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

Question

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

我不知道什么是错的，因为对我来说，它看起来功能一样的程序张贴在这里：Printing prime numbers from 1 through 100 有一些细微的变化（输入一个号码，改变“我”，以数小于输入）。

我一直在寻找过去的三四天，我还没有找到任何真正完全回答这个问题的东西，达到我需要的程度。任何帮助深表感谢。

#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

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; 
     } 
    } 
} 

上面的代码不会显示质数，它只会告诉你输入的号码，如果/当你遇到一个除数不是数量的因素。例如，如果输入“9”，则将从2开始，这不是9的因子，因此，如果不是9，则会显示“9”（错误地）为“素数”。

测试数字是否为素数的最简单方法是检查所有低于平方根的素数，看它们是否是给定数字的因子。如果它们都不是（然后没有一个低于给定数字的非素数），那么这个数字就是一个素数。如果它至少有一个素数因子小于或等于它的平方根，那么它不是素数。

由于您希望显示[0，X]范围内的所有素数，因此您可以简单地检查一下您的因素列表（或者相反，这实际上是Eratosthenes的Sieve ）。

Answer 2

我认为在你的答案任何方式一次循环将终止（我说的循环检查是否是总理或不），一旦它出来，你不知道它是否做出了决定。所以努力创造一个标志变量，并检查outside.I OPE，将工作

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); 
} 

Answer 3

当我的观点是喜欢你一个，我写了这个代码，它的工作。希望它能帮助你。

#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; 
} 

Answer 4

您应该使用埃拉托色尼的筛计算素数小于ñ。首先列出所有数字从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 

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

Answer 5

一个简单的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; 
    } 

Answer 6

只是一个小建议。由于素数是奇数，偶数可以省略。 例如，在下面的循环中，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; 
     } 
    } 

Answer 7

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); 
} 

Answer 8

人，我想我有这个最简单的梅索德所有。希望对你有帮助！

#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; 
}