3

昨日、C++ に関する本を読み始めました。これまでのところ、私は 100 ページで、その数を使って最初のプログラムを書きました。与えられた数が素数かどうかを調べたいと思っていました。

それについて2つ質問があります。

  1. 私は自分の方法が良いこと以外のすべてであることを知っています. プログラムは、プログラムを大きくするすべての数値をチェックしています。これを行う理想的な方法は何ですか？あなたの答えをまだ理解しているかどうかは関係ありません。後でコマンドを読み上げます:)。

  2. 回線に大きな問題がありました"Result+=1"。最初に を持っていたi=1ので、数値 に対して次の結果が得られました7。

    1111112

まあ、私もその理由を知っています。最初の 6 つの for ループで 1 つの数字(1)と最後の 1 つを見つけました2(1,7)。しかし、それは明らかに私が望んでいた方法ではありません。Result をある種のカウンターにしたい。それ、どうやったら出来るの？

コード：

#include <iostream>
using namespace std;



// Hauptprogramm

int main ()
{
    // Variablen
    int Prime_number;
    int Result = 0;

    // Abfragen
    cout << "Please enter possible prime number: ";
    cin >> Prime_number;

    // Rechnen
    for (int i=2; i <= Prime_number ; i++)
    {   
            if (Prime_number%i == 0)
            {   
                    Result +=1;
            }
    }

    // Ausgabe
    if(Result == 1)
    {
            cout << "You got a prime number!" << endl;
    }
    else
    {
            cout << "No luck" <<endl;
    }

    return 0;
}
4

5 に答える 5

3

あなたの論理は奇妙で、あなたが言うように非常に非効率的です。これはより良いロジックです

2 から Prime_number - 1 までのすべての数をチェックし、それらのいずれかが正確に割り切れる場合、それは素数ではなく、そうでない場合は素数です。重要な点は、除数を 1 つ見つけたら探すのをやめるということです。なぜなら、質問に対する答えがわかるからです。これを行うコードを次に示します

bool prime = true;
for (i = 2; i < Prime_Number; ++i)
{
    if (Prime_Number % i == 0)
    {
        prime = false;
        break;
    }
}
if (prime)
    cout << "You got a prime number!" << endl;
else
    cout << "No luck" <<endl;

あなたの試みで見逃した2つのポイントは、変数の使用と、ループが終了したことを知ったらループから抜け出すboolことができるという事実だと思います。break

ところで、このコードはさらに改善することができますが、それはあなたのための演習です。

于 2012-11-03T08:39:38.277 に答える
0

次のコードも確認できます。

#include "time.h"
#include "iostream"
#include "conio.h"
using namespace std;

int main()
{
    div_t divresult;
    time_t t1,t2;   
    t1 = time(NULL); 
    int prime[1501] = {0};
    prime[1] = 2;
    prime[2] = 3;
    prime[3] = 5;
    prime[4] = 7;
    prime[5] = 11;
    int count = 6;

    for(int i = 12; count < 1500; i +=1)
    {
        bool Bprime = true; 
        for(int j = 1; j < count; j+=1)
        {
            if(i%prime[j] == 0) Bprime = false;
        }
        if(Bprime == true) prime[count++] = i;
    }
    t2 = time(NULL);
    divresult = div(t2-t1,60);
    cout<<divresult.quot <<" min "<<divresult.rem<<" sec"<<endl;
    int n = 0;
    cout<<"Give Value of N:";
    cin>> n;
    cout<<n<<"th prime is: "<<prime[n-1]<<endl;     

    _getch();
    return 0;
}
于 2012-12-20T11:32:01.540 に答える
0

あなたの質問に関して、あなたの方法はかなり堅実だと思います：

なぜ i=2 から始めるのですか?

私の素数の定義は、1 とそれ自体の 2 つの因数を持つ数です。したがって、1 つから開始すると、prime_number は正確に 1 で割り切れるため、余分な要素を (正しく) カウントします。これにより、2 つの要素が見つかったため、結果カウントは 2 になります。

より良い方法は何ですか？

より良い方法がいくつかありますが、かなり複雑なものもあります。ただし、現在のアルゴリズムは、いくつかの直接的な方法で簡単に改善できます。

  • 1 でも素数でもない因数を見つけるとすぐに、その数が素数ではないことがわかります。任意の (primenumber%i)==0 になるとすぐに、IsPrime=false のようなフラグを設定し て、ループから抜け出すことができます。 .
  • 素数の場合でも、可能な最大の因数は素数/2 であるため、実際には素数まで上げる必要はありません。この場合、ループは 2 倍高速になり、同様に機能します。2. 編集: 実際、少し考えてみると、素数の平方根は十分な制限です。なぜなら、すべての因数がペアになり、小さい方の因数が常にこの制限内にあるからです。

楽しく学んでいただければ幸いです。

于 2012-11-03T08:36:41.870 に答える
0 
#include <stdio.h> 
#include <cmath>

bool BePrime(unsigned int N){
    if(N == 2) return true;

    for(int i = 2; i <= int(sqrt(N)); i++) {
        if(N%i == 0) return false;
    }
    return true;
}

main(){
    int a;
    while(scanf("%d",&a)){
        if(BePrime(a)) {
            printf("%d is Prime\n", a);
            continue;
        }
        printf("%d is not Prime\n", a);
    }

}
于 2015-03-21T04:42:39.500 に答える