c - C中的素数优化

Question

我尝试打印素数；2到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 模任何数都是 1。

最后。sr 永远不会等于 num2，因为 sr 是 1 而 num2 是 2 或更大，所以它永远不会打印任何东西。

这会让你进入一个什么都不做的无限循环

Answer 2

如果你想优化它，你应该使用像eratosthenes筛子这样的东西。它很容易在你的数据范围内操作。你可以在这里阅读更多关于它的信息： http ://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Answer 3

    #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 来优化代码。

Answer 4

您可以使用的一种优化是，所有大于 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。