c - Cでの素数の最適化

Question

私は素数を印刷しようとします。200万から100万。しかし、コンソールには何も印刷されませんでした。私のコードを確認してもらえますか？そして、どうすればこのコードをより最適化できますか？

これが私のコードです：

#include <stdio.h>
#include <math.h>

main()
{
   int num, sr, num2;

   for (num = 2; num <= 1000000; num++) {
      sr = (int) sqrt(num);
      for (num2 = 2; sr % num2 != 0; num2++) {
         if (sr == num2) {
            printf("%d\n", sr);
         }
      }
   }

}

Answer 1

コンパイルされましたか？

4行目: main()?int main()

別のこと: sr = 1. 1 modulo 任意の数は 1.

そして最後に。sr が 1 で num2 が 2 以上であるため、sr が num2 と等しくなることはなく、何も出力されません。

これにより、何もしない無限ループに陥ります

Answer 2

最適化したい場合は、エラトステネスのふるいのようなものを使用する必要があります。データ範囲を操作するのは簡単です。詳細については、こちらをご覧ください: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Answer 3

使用できる最適化の1つは、3を超えるすべての素数が6n + 1または6n-1の形式であり、数値が素数で割り切れる場合、それは素数ではないという事実です。その事実を使用するコードを次に示します。

#include <stdio.h>
#include <math.h>

int is_prime(long num)
{
    int k = 1, a = 0, b = 0;
    long sr;
    switch(num)
        {
        case 1: return 0;
        case 2: return 1;
        case 3: return 1;
        case 4: return 0;
        case 5: return 1;
        case 6: return 0;
        case 7: return 1;
    }
    if (num % 2 == 0) return 0;
    if (num % 3 == 0) return 0;
    sr = (int) sqrt(num);
    while (b < sr) {
        a = (6 * k) - 1;
        b = (6 * k) + 1;
        if (num % a == 0)
            return 0;
        if (num % b == 0)
            return 0;
        k += 1;
    }
    return 1;
}

void main(void)
{
    int j;

    for (j = 0; j<100; j++){
        if (is_prime(j))
            printf("%d is a prime\n", j);
    }
}

numが素数の場合、この関数は1を返します。

Answer 4

    #include <stdio.h>
    #include <math.h>

    int main(){
    int num, sr, num2;
    int isPrime = 1; // this is a check parameter; isPrime = 0 if number is not prime.
    for(num=2; num<=100; num++){
        sr = (int) sqrt(num);
        for(num2=2; num2 <= sr; num2++){
            //num2 <== sr to stop the innner loop
            if(num%num2 == 0){
                //printf("=========== %d|%d\n", num,num2); // uncomment this to see if a number is divisable
                isPrime = 0; // this number is not prime, cos num can be divided by num2
                break;
            }
        }
        if(isPrime){
            printf("Prime number is %d\n", num);
            isPrime = 1; // reset the check parameter
        }else{
            isPrime = 1; // reset the check parameter
        }
    }
         return 0;
    }

このコードは機能します。動作するので、遊んで最適化してみましょう。お知らせいただけない場合。私たちはあなたを助けようとします。

sqrt を使用してコードを最適化する方法が気に入っています。