与えられた値まで素数を見つけるための最適化方法n

Question

私はk=3からn（上の値を与えられます）から、値kごとにこの関数を使ってチェックしています。アレイ内のすべての素数をnまで取るように最適化するにはどうすればいいですか？各番号0​​を確認する必要はありませんか？

int primeCheck(long long int k) { 
    int j; 
    int isPrime = 1; 
    int sr = (int)sqrt(k); 
    for (j = 2; j <= sr; j++) { 
     if (k % j == 0) { 
      //printf("=========== %d|%d\n", num,num2); // uncomment this to see if a number is divisible 
      isPrime = 0; // this number is not prime, cos num can be divided by num2 
      break; 
     } 
    } 
    if (isPrime) { 
     return isPrime; // reset the check parameter 
    } else { 
     return 0; // reset the check parameter 
    } 
    return 0; 
} 

Answer 1

は、エラトステネスのふるいをお試しください。このアルゴリズムは、2からnまでの素数のすべての因子を排除することによって機能します。

int main() { 
    int n; 
    scanf("%d", &n); 
    int prime[n+1]; 
    for(int i = 0; i < n+1; i++) 
     prime[i] = 0; 

    for(int i = 2; i <= sqrt(n+1); i++) { 
     if(prime[i] == 0) { 
      for(int j = i*i; j <= n; j += i) 
       prime[j] = 1; 
     } 
    } 

    int prime_list[n], size = 0; 
    for(int i = 2; i <= n; i++) { 
     if(prime[i] == 0) 
      prime_list[size++] = i; 
    } 
} 

例えば数は当初なりましょう：

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

• を（2を除く）2のすべての倍数を削除する我々が得る：

2 3 5 7 9 11 13 15 17 19 21 23 25 27 29

3（ 3を除く）のすべての倍数を削除する

• 、我々が得る：

2 3 7 11 13 17 19 23 29

： 5（ 5を除く）のすべての倍数、我々が得るを削除

2 3 5 7 11 13 17 19 23 25 29

• これ以上の削除はなくなり、残った素数の繰り返しをもう少し繰り返すと、これが最終的なリストになります。

  prime[i]i = {2, 3, 7, 11, 13, 17, 19, 23, 29}です。コードで行われているように、これらのすべてのインデックスを別のprime_listベクターに追加します。このベクトルは、[2, n]からすべての素数を与えます。

Answer 2

あなたは私がエラトステネスアルゴリズムのふるいを推奨範囲内の数字の多くを確認したい場合も

int primeCheck(long long int k){ 
    if(k<=1 || k%2==0){ //if number is even return 0 its not prime 
     return 0; 
    } 

    int sr = (int) sqrt(k); //probable divisor 

    for(int j=3;j<=sr;j+=2){ 
     if(k%j == 0){ 
      //printf("=========== %d|%d\n", num,num2); // uncomment this to see if a number is divisable 
      return 0; //if number is not prime skip everything and return zero 
     } 
    } 
    return 1; //if loop completes i.e. not divisor found then return return 1 
} 

Answer 3

のような2.何かの後に偶数をスキップすることができます。

あなたの関数は少し良いかもしれません：

int primeCheck(long long int n) 
    { 
     if (n <= 1) 
     { 
      return 0; 
     } 
     if (n <= 3) 
     { 
      return 1; 
     } 
     if (n % 2 == 0 || n % 3 == 0) 
     { 
      return 0; 
     } 
     int sr = (int)sqrt(n); 

     for (int i = 5; i <= sr; i += 6) 
     { 
      if (n % i == 0 || n % (i + 2) == 0) 
      { 
       return 0; 
      } 
     } 
     return 1; 
    }