Algorytm liczby pierwsze

[morfeusz1]

Prosiłbym o podpowiedzi/rozwiązanie do następującego zadania: Algorytm wypisujący liczby pierwsze, których iloczyn jest równy zadanej liczbie \(\displaystyle{ n>0}\)

[Afish]

Poczytaj o rozkładzie na czynniki pierwsze (faktoryzacji).

[norwimaj]

Gdybym umiał napisać program, który szybko rozkłada liczbę na czynniki pierwsze, to raczej nie chwaliłbym się tym na forum, tylko bym korzystał. Dlatego nie licz na satysfakcjonującą odpowiedź.
Na szczęście jest spora szansa że nikt nie potrafi, więc nasze pieniądze w bankach wydają się bezpieczne.

[Xitami]

A jak wielkie może być N?

[morfeusz1]

Nie podano w zadaniu więc obojętnie jakie będzie

[kokosek]

Skoro masz napisać algorytm, a nie program, to wielkość \(\displaystyle{ n}\) nie ma znaczenia.
Tak więc podpowiedź Afisha + Google i tyle.

[Xitami]

Eratostenesowym sitkiem wycedziłem liczby pierwsze do pierwiastka z N
Korzystając z sita sprawdzam podzielność tylko przez liczby pierwsze < sqrt(N)
Jeżeli nie dzieli się przez żadną z nich to znaczy, że N jest liczbą pierwszą
Jeżeli znalazłem liczbę K przez którą N się dzieli, sprawdzam czy N/K jest liczbą pierwszą
W teście na pierwszość oczywiście korzystam z utworzonego już sita jako źródła podzielników

Na ideone.com 1000 razy test(4294049777) zająło 0,2 sekundy
1000 razy test(1073217479) 0,1 sekundy mHNVQ

[Afish]

Można też tym

[Xitami]

Można też tym

a co z np. 999974077=15161*65957
Brent trochę to ulepszył, rzadziej rozkłada ręce.
Wtedy czasem rho pomaga ale czy zawsze?-- 14 marca 2011, 01:23 --Testowanie pierwszości można zrealizować np. tak:

Kod: Zaznacz cały

int CzyPierwsza(int n){ // zwraca 1 jeżeli N jest liczbą pierwszą 
   //  bez mnożenia i dzielenia !!!
        int a,b,k=n-1,s=n-1, z=n-2;
        while(z>1){
                a=s;k=0;b=z;
                while(b){
                        if(b&1){
                                k+=a;
                                if(k>=n) k-=n;
                        }
                        a+=a;
                        if(a>=n) a-=n;
                        b>>=1;
                }
                if(k==0) return 0;
                s=k;
                z--;
        }
        return k+1==n;
}