Простые числа до числа

Question

Я действительно новичок в C ++ и работаю над книгой Программирование: принципы и практика использования C ++. Работали над проблемой, чтобы найти все простые числа между 1 - данным пользователем номером. Теперь я получил эту часть вниз. Теперь я понимаю, что sqrt (i) сделает цикл короче, но я не уверен, что нужно проверить, чтобы узнать, является ли оно простым или нет в моих операторах if - else.

#include<vector>
#include<iostream>
#include<cmath>

using namespace std;

int main(){    
    vector<double> prime_numbers;
    double num;

    cout << "Please enter a number so we can find the primes for it: " << flush;
    cin >> num;

    for (int i = 2; i <= num; i++) {
        for (int j = 2; j <= i; j++) {
            // cout << sqrt(i) << "\t";

            // Check to see if Value of i is incremented correctly
            // Check to see if value of j is incremented properly before returnign to i
            //cout << i <<"\t" << j << endl;       

            if (j == i) {
                prime_numbers.push_back(i);
            }
            if (i % j == 0) {
                break;
            }   

        }   
    }
    for (double x : prime_numbers)
        cout << x << " | ";

    return 0;
}

Answer 1

Разница в том, что ваше предыдущее условие первичности - i == j - больше не выполняется.

Это верно именно тогда, когда вы проверили каждое число от 2 до i, но с пределом sqrt(i) вы выходите из цикла гораздо раньше.

Я думаю, что самое простое изменение - ввести переменную и переместить push_back вне цикла (это работает с любым из условий цикла):

for (int i = 2; i <= num; i++) {
    bool isPrime = true;  // Assume 'i' is prime until proven wrong.
    for (int j = 2; j <= sqrt(i); j++) {
        if (i % j == 0) {
            isPrime = false;
            break;
        }   
    }
    if (isPrime) {
        prime_numbers.push_back(i);
    }
 }

То есть сначала решите, имеет ли место что-то, затем сделайте что-нибудь с этой информацией.
Это полезный дизайн в очень многих случаях.

Например, гораздо проще перенести проверку простоты в функцию:

bool isPrime(int x) { /* something */ }

// ...

for (int i = 2; i <= num; i++) {
    if (isPrime(i)) {
        prime_numbers.push_back(i);
    }
}

Answer 2

Очень эффективный способ найти простые числа от 0 до n - использовать сито Эратосфена, есть много способов сделать это, вот пример:

vector<bool> v(n, true);
v[0] = v[1] = false;
for (int i = 2; i*i < n; i+= 2){
    if (v[i]) {
        for (int k = i*i; k < n; k += i) {
            v[k] = false;
        }
        if (i == 2)i = 1;
    }
}
for(auto i = 0; i < n; ++i)
      if(v[i])cout << i << ' ';
cout << endl;