Algoritmi → Matematički algoritmi → Prosti brojevi na intervalu

Prosti brojevi na datom intervalu – rešenje

Postavka

Učitavaju se dva prirodna broja a i b (a ≤ b). Ispiši sve proste brojeve iz intervala [a, b], po deset u jednom redu.

1 30

2 3 5 7 11 13 17 19 23 29

Ideja

Broj je prost ako je veći od 1 i nema delilaca osim 1 i sebe. Delioce je dovoljno tražiti do √b: ako b = d · e i d > √b, onda je e < √b i taj manji delilac bismo već našli. Zato je uslov petlje d * d <= b.

Za veliki interval (na primer do 10⁷) brže je Eratostenovo sito.

Rešenje (C++)

#include <iostream>
using namespace std;

bool prost(long long b) {
    if (b < 2) return false;              // 0 i 1 nisu prosti
    for (long long d = 2; d * d <= b; d++) // dovoljno je proveriti delioce do korena
        if (b % d == 0) return false;
    return true;
}

int main() {
    long long a, b;
    cin >> a >> b;
    int c = 0;                            // broj ispisanih prostih brojeva
    for (long long i = a; i <= b; i++) {
        if (prost(i)) {
            cout << i;
            c++;
            cout << (c % 10 == 0 ? "\n" : " ");   // po 10 u redu
        }
    }
    if (c % 10 != 0) cout << "\n";
    return 0;
}