-1

ユーザーが入力した 3 と整数 'x' の間の素数を決定して出力する C++ プログラムに取り組んでいます。これには二重のネストされたループが必要であると想定しています.1つは3からxまで反復し、もう1つは数値が素数であるかどうかを確認します。2からx-1にするようなことをする必要があると思いますか? これを構文的に行う方法が本当にわかりません。助けてくれてありがとう！:)

編集:これは私が持っているものです:

#include <iostream>
#include <cmath>

using std::cout;
using std::endl;
using std::cin;

int main(){

   int x;
   int i;
   int j;

   cout << "Please enter an integer 'x' greater than 3: " << endl;

   cin >> x;

   if (x <= 3){

        cout << "Please enter new value 'x' greater than 3: " << endl;

        cin >> x;
   }
        for(int i=3; i<=x; i++){
                for(j=2; j<i; j++){
                   if(i%j == 0)
                        break;
                   else if(i == j+1);
                        cout << i << endl;
                   }
        }
        return 0;
}

そして、「x」として 10 を入力すると、出力が得られます: 3 5 5 5 7 7 7 7 7 9

誰でもこれを修正する方法を教えてもらえますか?

4

3 に答える 3

1

十分に小さい場合は、エラトステネスのふるいXを使用してより効率的に行うことができます。これは、以前に破棄された素数のメモリを維持するため、「X までの素数」の場合に理想的です。これは、候補番号ごとに一連のフラグを保持することによって行われます。最初はすべて true に設定されています (もちろん 1 を除く)。

次に、最初の真の値 (2) を取り、それを素数として出力し、その倍数のすべてのフラグを false に設定します。

次に、続行します。

  • 3;
  • 5 (4 は 2 の倍数であるため);
  • 7 (6 は 2 と 3 の倍数であるため);
  • 11 (8 と 10 は 2 の倍数、9 は 3 の倍数であるため);
  • 13 (12 は 2 の倍数であるため);
  • 17 (14 と 16 は 2 の倍数であり、15 は 3 と 5 の倍数であるため);
  • 等々。

擬似コードは次のようになります。

def showPrimesUpTo (num):
    // create array of all true values

    array isPrime[2..num] = true

    // start with 2 and go until finished

    currNum = 2
    while currNum <= num:
        // if prime, output it

        if isPrime[currNum]:
            output currNum

            // also flag all multiples as nonprime

            clearNum = currNum * 2
            while clearNum <= num:
                isprime[clearNum] = false
                clearNum = clearNum + currNum

        // advance to next candidate

        currNum = currNum + 1

それ以外の場合は、提案に従って試行分割を行うことができます。基本的な考え方は、2 から目標数の平方根までの各数値をチェックして、それが倍数かどうかを確認することです。疑似コードでは、次のようになります。

def isPrime (num):
    // val is the value to check for factor

    val = 2

    // only need to check so far

    while val * val <= num:
        // check if an exact multiple

        if int (num / val) * val == num:
            return false

        // no, carry on

        val = val + 1

    // if no factors found, it is a prime

    return true

平方根までチェックするだけでよい理由は、その上に係数が見つかった場合、平方根の下に対応する係数がすでに見つかっているからです。

たとえば、3 x 17です51。51が素数かどうかを調べるために 2 から 50 までの数をチェックしている場合、3最初に が見つかります。つまり、 をチェックする必要はありません17。

于 2013-01-29T02:53:07.657 に答える
0

これはかなり高速で効率的だと思います

 int main(){
    for(int i=3; i<=X; i++)    
            if(IsPrime(i)){
               cout<<i<<endl;
            }
    }

 bool IsPrime(int num){
    /* use commented part if want from 2
        if(num<=1)

            return false;

        if(num==2)

            return true;
    */
        if(num%2==0)

            return false;

        int sRoot = sqrt(num*1.0);

        for(int i=3; i<=sRoot; i+=2)

        {

            if(num%i==0)

                return false;

        }

        return true;
    }
于 2013-01-29T02:56:28.920 に答える
0 
int main (char argv) 
{
    int tempNum = atoi(argv);
    for (int i=3; i<=tempNum; i++) 
        for (int j=2; j*j<=i; j++)
        {
            if (i % j == 0) 
                break;
            else if (j+1 > sqrt(i)) {
                cout << i << " ";

            }

        }   

    return 0;
}

1 から 100 までの素数の出力 基本的にはこれですが、変更されています

于 2013-01-29T02:51:40.730 に答える