проблема в простом алгоритме в C - PullRequest
0 голосов
/ 22 июня 2011

После ответа @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 ()

так работает как надо?

Ответы [ 3 ]

1 голос
/ 22 июня 2011

Если вы хотите "генератор простых чисел", интерфейсы мне в порядке. Но ваш код ограничивает количество простых чисел.

бессмысленные интерфейсы не ценны. это может написать более просто.

#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;
}
1 голос
/ 22 июня 2011

Есть несколько логических ошибок:

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)
  }
}
0 голосов
/ 22 июня 2011

Вместо x = sqrt (n_limit) и if (n

...