C中素数算法的问题

Question

按照 @neal aise 此处获取素因数的答案： 我做了：

/*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 */
}

如何修改函数中的代码

printPrimeFactors()

那么它可以按预期工作吗？

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.

此外，通过停在 处，您只能打印出大约一半的素因数。要么将 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

您可以像 if(n*n < n_limit) 那样执行 x = sqrt(n_limit) 和 if(n < x) 操作。不需要昂贵的 sqrt()、float 或cast。