C++ 查找从 1 到输入的数字的所有质数
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/19454409/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
C++ finding all prime numbers from 1 to a number entered
提问by user2895469
So the point is to have the program find and list all prime numbers between 1 and the number you enter. I'm using number_test as the number tested for prime, and divisor and the number to divide by.
所以重点是让程序找到并列出 1 和您输入的数字之间的所有质数。我使用 number_test 作为测试素数、除数和要除数的数。
I'm not sure what's wrong, as to me it looks functionally the same as the program posted here: Printing prime numbers from 1 through 100with some minor changes (inputting a number, changing "i" to less than the number entered).
我不确定出了什么问题，对我来说，它在功能上与此处发布的程序相同：打印从 1 到 100 的素数，并进行一些细微更改（输入一个数字，将“i”更改为小于输入的数字）。
I've been looking for the past three or four days, and I haven't found anything that really answers this question fully, to the degree I need for class. Any help is much appreciated.
在过去的三四天里，我一直在寻找，但我没有找到任何可以真正完全回答这个问题的东西，达到我上课所需的程度。任何帮助深表感谢。
#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();
}
回答by user448810
You should use the Sieve of Eratosthenes to compute the primes less than n. Begin by making a list of all numbers from 2 to the maximum desired prime n. Then, at each iterative step, the smallest remaining number that hasn't yet been considered is output and all of its multiples are crossed off the list.
您应该使用 Eratosthenes 筛来计算小于n的素数。首先列出从 2 到最大所需素数n的所有数字。然后，在每个迭代步骤中，输出尚未考虑的最小剩余数字，并将其所有倍数从列表中划掉。
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
This O(n log log n) algorithm is very fast; you should be able to compute the 78498 primes less than a million in less than a second.
这个 O(n log log n) 算法非常快；您应该能够在不到一秒的时间内计算出小于一百万的 78498 个素数。
回答by Dineshkumar Ponnusamy
A simple C++ Program to find the "N" prime numbers.
一个简单的 C++ 程序来查找“N”个素数。
#include <iostream >
using namespace std;
int main()
{
int N;
cin >> N;
for (int i = 2; N > 0; ++i)
{
bool isPrime = true ;
for (int j = 2; j < i; ++j)
{
if (i % j == 0)
{
isPrime = false ;
break ;
}
}
if (isPrime)
{
--N;
cout << i << "\n";
}
}
return 0;
}
回答by PeterSmith
Just a small suggestion. Since prime numbers are odd, even numbers can be left out. For example, in below loops, i and j increase by 2 (i +=2) instead of by 1 (i ++).
只是一个小建议。由于素数是奇数，偶数可以省略。例如，在下面的循环中，i 和 j 增加 2 (i +=2) 而不是增加 1 (i ++)。
for (int i=3;i<=numberByUser; i+=2){
for (j=3;j<=i;j +=2){
if (i%j==0){
break;
}
}
回答by Bipin B
i think in your answer any way one time the loop will terminated(i am talking about the loop checking the whether it is prime or not)once it comes out you don't know whether it made the break or not.So try to make a flag variable and check outside.I ope that will work
我认为在你的回答中，有一次循环将终止（我说的是循环检查它是否是素数）一旦它出现你不知道它是否中断了。所以试着做一个标志变量并在外面检查。我认为这会起作用
for(n=lower+1; n<upper; n++)
{
prime = 1;
for(i=2; i<n; i++)
if(n%i == 0)
{
prime = 0;
break;
}
if(prime)
printf("\n\n\t\t\t%d", n);
}
回答by Bipin B
When my point was like your one, I wrote this code, it worked. Hope it will help you.
当我的观点和你的观点一样时，我写了这段代码，它奏效了。希望它会帮助你。
#include <cstdio>
#include <vector>
using namespace std;
vector <int> sn;
bool isPrime(int n) {
if (n <= 1) {
return 0;
}
if (n == 2) {
return true;
}
if (!(n % 2)) {
return false;
}
for (int i = 2; i*i <= n; i++) {
if (!(n % i)) {
return 0;
}
}
return 1;
}
void primeNumbers(int k) {
sn.push_back (2);
int i = 3, j = 1;
for ( ; j < k + 1; i += 2 && j++) {
if (isPrime(i)) {
sn.push_back(i);
}
}
}
int main() {
int i, k;
scanf("%d", &k);
primeNumbers(k);
for (i = 0; i < sn.size(); i++) {
printf("%d ", sn[i]);
}
return 0;
}
回答by Zac Howland
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;
}
}
}
The above code will not show you the prime numbers, it will just show you the number you entered if/when you run into a divisor that is not a factor of the number. For example, if you enter "9", you will start at 2, which is not a factor of 9, so you will show "9" (incorrectly) as a "prime", when it is not.
上面的代码不会显示质数，它只会显示你输入的数字，如果/当你遇到一个不是数字因数的除数。例如，如果您输入“9”，您将从 2 开始，这不是 9 的因数，因此您将“9”（错误地）显示为“素数”，而如果不是。
The easiest method for testing if a number is a prime is by checking all prime numbers below it's square root to see if they are factors of the given number. If none of them are (then none of the non-prime numbers below the given number will be either), the number is a prime number. If it has at least one prime factor less than or equal to it's square root, it is not prime.
测试一个数是否为素数的最简单方法是检查其平方根以下的所有素数，看它们是否是给定数的因数。如果它们都不是（那么给定数字以下的非质数都不是），则该数字是质数。如果它至少有一个质因数小于或等于它的平方根，则它不是质数。
Since you are looking to show all primes in a range of [0, X], you can simply check your list of factors as you go along (or do it in reverse, which is effectively what the Sieve of Eratosthenes does).
由于您希望显示 [0, X] 范围内的所有素数，您可以在进行时简单地检查因子列表（或反向进行，这实际上是 Eratosthenes 筛法所做的）。
回答by Rohit Arora
int getNumberOfPrimes(int N) {
bool *numbers = new bool[N-1]();
for (int i = 2; i <= N/2; ++i) {
if (numbers[i-2] == true) continue;
for (int j = i+i; j <= N; j = j+i) {
numbers[j-2] = true;
}
}
int count = 0;
for (int i = 0; i < (N-1); ++i) {
if (numbers[i] == false) ++count;
}
delete []numbers;
return(count);
}
回答by Coprean Vlad
Man I guess I have the simplest methode of this all. Hope it works for you!
伙计，我想我有最简单的方法。希望这对你有用！
#include < iostream >
using namespace std;
int main()
{
int n, i, j
cin>>n; //The max limith
for(i=2; i<=2; i++)
{
for(j=1; j<=i/2; j++)
if(i%j!=o)
cout<<i;
}
return 0;
}
回答by Youssef Essam
If a number has divisors, at least one of them must be less than or equal to the square root of the number. When you check divisors, you only need to check up to the square root, not all the way up to the number being tested.
如果一个数有除数，则其中至少有一个小于或等于该数的平方根。当您检查除数时，您只需要检查平方根，而不是一直检查到被测试的数字。
