c - 使用 C 查找素数不起作用
问题描述
我目前正在学习 C 并试图解决一个问题。我需要使用数组和循环找到从 2 到 100 的所有质数。
我已经知道这个问题的解决方案,但是我无法在我的代码中找到错误。这是我第一次使用 StackOverflow,所以希望我正确评论了所有内容:)
#include <stdio.h>
#include <stdlib.h>
int main(){
int prime_numbers[50] = {2,3}; //initializes the array which will be printed at the end
int counter = 1; //initializes the index of the last prime element in array
int checker = 0; //initializes a checker used to determine if the number is prime
for(int i = 5; i <= 100; i++) { //goes through numbers 5 to 100 as the first two primes are hard coded
for(int j = 0; j <= counter; j++){ //goes through array untill it reaches last prime using the before initialized counter
if(i % prime_numbers[j] != 0) { //check to see if a number that is being checked is not divisible by j'th element in array
checker++; //if so, checker is incremented
}
if(checker == counter + 1) { //check to see if number was not divisible by any prime in our array
checker = 0; //if so checker is reset to 0 for the next iteration
++counter; //counter is incremented as there is one more prime in our array
prime_numbers[counter] = i; //add inside array the found prime number
break; //break should not be necessary, however for some reason, it yields a different result when I don't put it in
} //most likely the error in the code. Need to find out why loop does not stop after second if is done
}
}
for(int g = 0; g <= 50; g++) { //prints out all the prime numbers in array
if(prime_numbers[g] != 0) {
printf("%d ", prime_numbers[g]);
}
}
return 0;
}
我希望程序打印从 0 到 100 的所有素数,中间有空格。
解决方案
该程序还查找非质数。它的逻辑是一个相当奇怪的倒置。候选者只需要被数组中的一个素数整除。报告还打破了数组界限。
更正后的代码:
#include <stdio.h>
int main(void) { // correct function signature
int prime_numbers[50] = {2,3};
int counter = 1;
int checker; // initialise within each loop
for(int i = 5; i <= 100; i++){
checker = 0; // inintialise here
for(int j = 0; j <= counter; j++) {
if(i % prime_numbers[j] == 0) { // opposite test to yours
checker++; // flag a non-prime
break;
}
}
if(checker == 0) { // moved outside the loop
++counter;
prime_numbers[counter] = i;
}
}
for(int g = 0; g < 50; g++) { // corrected the bounds error
if(prime_numbers[g] != 0){
printf("%d ", prime_numbers[g]);
}
}
printf("\n"); // flush the output buffer
return 0;
}
程序输出:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
报告循环依赖于初始化为0
s 的数组,更好的方法是
for(int j = 0; j <= counter; j++) {
printf("%d ", prime_numbers[j]);
}
printf("\n");