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