cpp

[Bogus]

Napisz program w języku C++, który dla dowolnej liczby naturalnej n wypisze na ekranie jej dzielniki będące liczbami pierwszymi.

[matshadow]

Kod: Zaznacz cały

#include<iostream>
using namespace std;
bool prime(int n)
{
	for(int i=2;i*i<=n;i++)
	 if(n%i==0)
	  return false;
	return true;
}

main()
{
    ios_base::sync_with_stdio(0);
    int n;
    cin>>n;
    if(n%2==0)
	 cout<<2<<" ";
    for(int j=3;j<=n;j+=2)
	 if(n%j==0&&prime(j))
	  cout<<j<<" ";
	cout<<endl;
    system("pause");
}

[Dumel]

a jak zależy Ci na elegancji i wydajności (choć w takim prostym programie nie ma ona zbyt wielkiego znaczenia), to można najpierw walnąć sito Eratostenesa a potem sprawdzać kolejne liczby pierwsze

[Xitami]

Jeżeli typ "int" jest 32-bitowy, to nawet w "takim prostym programie" wydajność ma znaczenie!
Ile czasu będzie trwało sprawdzenie sporej liczby, powiedzmy 2000000000?

W teście fajnie, sprawdzane są potencjalne dzielniki tylko do pierwiastka,
ale w "main()" sprawdzane są aż do "n", a to w porywach 65 TYSIĘCY RAZY za dużo!
Jeżeli znalazłem dzielnik (j), to także "n/j" jest dzielnikiem "n"

Ale czy test "pierwszości" w ogóle jest potrzebny?
Jeżeli znalazłem dzielnik, to puki n%j==0 dzielę n przez j.
Wtedy nie muszę się bać, że j będzie liczbą złożoną.
Kończę gdy j*j>n. uwaga - w n może coś zostać.

Sito dobry pomysł, wystarczy do 65537 a może nawet mniej .