c - C中素数算法中的问题

Question

遵循@neal aise here的回答以获得主要因素：我做到了：

/*neal aise's  code*/
printPrimeFactors(int num) {
  int i;
  for (i = 2; i < sqrt(num); i=next_prime(i)) {
     if (num %i){
        printf("%d", i);
     }
  } 
}

/*my code*/
int next_prime(int p){
   int prime_found = 0; 
   while (!prime_found){
    if (p <= 1)/* if low number comes in, then */
       p = 2; /* next prime is always 2 (first prime) */
    else
          if ((p % 2) == 0) /* no even primes */
              p++;      /* make the number odd before test */
          else
              p += 2;       /* get next odd numero to test */
    prime_found = is_prime(p); /*check if number is prime*/
    }
    return (p);
}


int is_prime(int p){
    int curr_num = 2;                  /* start divisor at 2 */
    float stop_num = sqrt((float) p);  /* no divisor > sqrt of number needed */    
    while(curr_num <= stop_num){
        if ((p % curr_num) == 0)      /* not prime if evenly divisible */
            return (0);
        else
            curr_num++;              /* increment divisor */
    }
    return(1);                         /* not evenly divisible, return prime */
}

如何修改函数中的代码

打印素数（）

所以它可以按需要工作吗？

Answer 1

如果你想要“素数生成器”，接口对我来说没问题。但是您的代码限制了素数的数量。

无意义的接口没有价值。它可以写得更简单。

#include <stdio.h>

int main() {
  int n, m;
  for (n = 1; n < 1000 /* specify your max */; n++) {
    for (m = n-1; m > 1; m--)
      if (n % m == 0) break;
    if (m == 1)
      printf("%d\n", n);
  }
  return 0;
}

Answer 2

有几个逻辑错误：

if (num%i) // Change this to...
if ((num%i)==0) // num%i == 0 when i divides num, this 'i' is a prime factor.

此外，在 停止时，您只会打印出大约一半的主要因素<sqrt(num)。将 for 循环的退出条件更改为i <= num：

for (i = 2; i <= num; i=next_prime(i)) { // note the <=
  if (num %i){
     printf("%d ", i);
  }
}

或者另一种更有效的方法。请注意，这些因素不是按顺序排列的：

for (i = 2; i <= sqrt(num); i=next_prime(i)) {
  if (num %i){
     printf("%d %d ", i, num/i); // Print out the pair, since we stop at i<=sqrt(num)
  }
}

Answer 3

代替 x = sqrt(n_limit) 和 if(n < x)，您可以像 if(n*n < n_limit) 那样做。不需要昂贵的 sqrt()、浮动或强制转换。