Na razie mam program które wypisuję dzielniki. Ale jak sprawdzić czy dzielnik jest liczbą pierwszą?
int main()
{
int liczba;
do{
cout << "Podaj liczbe naturalna\n";
cin >> liczba;
} while (liczba < 0);
for (int i = 1; i < liczba; i++) {
if (liczba % i == 0) {
}
}
}
Tu Masz sprawdzanie naiwne, niezbyt optymalne ~sqrt(n):
using ull = unsigned long long int ;
int isPrime(ull n) {
if (n <= 3) return n > 1;
else if (n % 2 == 0 || n % 3 == 0) return 0;
ull i = 5;
while (i * i <= n) {
if (n % i == 0 || n % i + 2 == 0)
return 0;
i += 6;
}
return 1;
}
Zamiast znajdować wszystkie dzielniki i filtrować te, które nie są pierwsze, wyznacz sobie faktoryzację liczby (algorytm masz tu https://en.wikipedia.org/wiki/Trial_division), po czym usuń duplikaty.
@Szymon137: "A nie da się jakoś za pomocą pętli w tym ifie?" Da się, warunek będzie wyglądał: (liczba % i == 0 && isPrime(i)).
typedef unsigned long long ULL;
vector<ULL> Prime(ULL n)
{
vector<bool> primes(n+1);
vector<ULL> ret;
for(ULL i=2;i*i<n;++i)
{
if(!primes[i])
{
for(ULL k=2*i;k<=n;++k) primes[k]=true;
if(!(n%i)) ret.push_back(i);
while(!(n%i)) n/=i;
}
}
return ret;
}