C++查找从1到输入数字的所有素数

Question

所以重点是让程序找到并列出1和你输入的数字之间的所有素数.我使用number_test作为测试素数,除数和除数的数字.

我不确定是什么问题,对我来说,它看起来在功能上与此处发布的程序相同:从1到100打印素数 并进行一些小的更改(输入数字,将"i"更改为小于输入的数字).

我一直在寻找过去的三四天,而且我没有找到任何能够完全回答这个问题的东西,达到我课堂上所需要的程度.任何帮助深表感谢.

#include iostream
#include conio.h
using namespace std;

void main(void){
//Declare variables
int number_entered;
//Get inputs    
cout << "This program lists all prime numbers from 1 through a positive number entered."
 << endl;
cout << "Please enter a positive integer."
 << endl;
cin >> number_entered;
cout << "Displaying all numbers from 1 to " << number_entered
 << endl
 << "Press any key to continue..."
 << endl;
getch();

for(int number_test = 2; number_test < number_entered; number_test++){
    for(int divisor = 2; divisor < number_test; divisor++){
        if(number_test % divisor == 0){
            break;
        }
        else if(number_test % divisor != 0){
            cout << number_test << " ";
            break;
        }
    }
}

getch();
}

Answer 1

您应该使用Eratosthenes的Sieve来计算小于n的素数.通过使所有号码的列表,从2最大的期望黄金开始ñ.然后,在每个迭代步骤中,输出尚未考虑的最小剩余数,并且将其所有倍数从列表中除去.

function primes(n)
    sieve := makeArray(2..n, True)
    for p from 2 to n step 1
        if sieve(p)
            output p
            for i from p*p to n step p
                sieve[i] := False

这个O(n log log n)算法非常快; 你应该能够在不到一秒的时间内计算出不到一百万的78498素数.