O πιο γρήγορος τρόπος να βρεις prime numbers in C

[kostasdi]

Ποιος πιστεύεται είναι ο πιο γρήγορος τρόπος να βρεις τους prime numbers σε ένα μεγάλο σύνολο αριθμών;(11 μέχρι 100000000)

Έψαξα λίγο και βρήκα

1)Sieve of Sundaram

2)Sieve of Atkin

3)Sieve of Eratosthenes

Έχετε να προτείνεται κανέναν άλλον;(και αν υπάρχει κάποιος που να μην χρειάζεται η υλοποίηση του arrays)

[Sheogorath]

Ψάχνεις μέχρι floor(root(Nmax)) και ελέγχεις και τα δύο πολλαπλάσια. 

[albNik]

Αν δηλώσεις πινάκα με πάνω από 40-50.000.000 αριθμούς πιθανόν να έχεις πρόβλημα μνήμης. 

Μπορεις να κάνεις sieve τμηματικά ανα 10.000.000. Ψάξε για segmented sieve των 1,2,3.

 

Ελέγχοντας καθε αριθμό αν διαιρείται απο 2 μέχρι floor(root) είναι πολύ αργός τρόπος.

[kostasdi]

Αν δηλώσεις πινάκα με πάνω από 40-50.000.000 αριθμούς πιθανόν να έχεις πρόβλημα μνήμης. 

Μπορεις να κάνεις sieve τμηματικά ανα 10.000.000. Ψάξε για segmented sieve των 1,2,3.

 

Ελέγχοντας καθε αριθμό αν διαιρείται απο 2 μέχρι floor(root) είναι πολύ αργός τρόπος.

ναι το σκέφτηκα αυτό αλλά προσπαθώ να βρω έναν τρόπο να το κάνω χωρίς πίνακες(δεν επιτρέπεται δυστυχώς)..και απλά επειδή είναι πολύ μεγάλα τα νούμερα προσπαθώ να αποφύγω όσες περισσότερες μετρήσεις μπορώ..πχ πολλαπλάσια 2,3,5

[Sheogorath]

Αν δηλώσεις πινάκα με πάνω από 40-50.000.000 αριθμούς πιθανόν να έχεις πρόβλημα μνήμης. 

Μπορεις να κάνεις sieve τμηματικά ανα 10.000.000. Ψάξε για segmented sieve των 1,2,3.

 

Ελέγχοντας καθε αριθμό αν διαιρείται απο 2 μέχρι floor(root) είναι πολύ αργός τρόπος.

Προφανώς μόνο τα μονά (ανα δύο κτλ) αλλά χωρίς πίνακες, πως?

[kostasdi]

Προφανώς μόνο τα μονά (ανα δύο κτλ) αλλά χωρίς πίνακες, πως?

άμα ήξερα ..καλά θα ήταν

μπορούμε να θεωρήσουμε ότι αν ένα αριθμός δεν διαιρείται  με το 2,3,5,7 είναι πρώτος;

[albNik]

Για καθε prime p  ισχυει  n^p-1%p=1.  Αυτη η πραξη (x^y mod z) λέγεται modPow και ειναι πολυ γρηγορη.   

Π.χ  για το p=5

2^5-1%5=1 

3^5-1%5=1

4^5-1%5=1 

 

 

Δυστυχώς ισχυει και για  λίγους non-prime (καπου 1 στους 10000) και λεγονται false-primes.

 

Δοκιμασε για ολους 11 μεχρι 100 000 000 το αποτελεσμα του 2^ν-1%ν και αν δεν ειναι 1 τοτε σιγουρα δεν ειναι πρωτος.

[Sheogorath]

άμα ήξερα ..καλά θα ήταν

μπορούμε να θεωρήσουμε ότι αν ένα αριθμός δεν διαιρείται  με το 2,3,5,7 είναι πρώτος;

Οχι, πχ το 121, που έχει ρίζα το 11 που είναι πρώτος

[V.I.Smirnov]

Οι αποτελεσματικοί τρόποι να ελεγχθεί αν ένας αριθμός είναι πρώτος και να παραγοντοποιηθεί αν χρειάζεται

χρησιμοποιούν ανώτερη άλγεβρα και είναι δυσνόητοι στο μέσο κοινό.

 

 

Δύο που θυμάμαι είναι ο "Miller-Rabin strong pseudoprime test base 2 και base 3" καθώς και ο έλεγχος Lucas.

Αυτοί είναι σωστά μονον για  n<10¹⁶  και ελέγχουν την primality χωρίς να παραγοντοποιούν.

 

Η παραγοντοποίηση (όχι μόνον έλεγχος) για μεγάλους ακέραιους είναι βραδύτερη.

Αλγόριθμοι που χρησιμοποιούνται είναι οι

- κόσκινο Pollard p-1,

- κόσκινο Pollard rho

- τετραγωνικό κόσκινο (quadratic sieve)

 

Για παραγοντοποίηση πολύ μεγάλων ακεραίων, ο καταλληλότερος αλγόριθμος

είναι η παραγοντοποίηση με ελλειπτική καμπύλη (Lenstra Elliptic Curve Factorization Method).

 

Τα παραπάνω και τα σχετικά τους μόνον για δυνατούς και θαρραλέους....

 

-

[kaliakman]

Είσαι πρωτοετής και είναι χωρίς πίνακες.. Απλά ψάχνεις διαιρέτες από το δυό μέχρι την ρίζα του αριθμού(Δεν είναι όλοι οι αριθμοί μέχρι τα 100.000.000 χρήσιμοι στο πρόγραμμα για να τους ελέγξεις).Το γιατί ψάξτο λίγο μόνος σου και αν δεν εδώ είμαστε(Αν δεν το καταλάβεις δεν θα ξέρεις να απαντήσεις άμα σε ρωτήσουν στον έλεγχο)

[Sheogorath]

Είσαι πρωτοετής και είναι χωρίς πίνακες.. Απλά ψάχνεις διαιρέτες από το δυό μέχρι την ρίζα του αριθμού(Δεν είναι όλοι οι αριθμοί μέχρι τα 100.000.000 χρήσιμοι στο πρόγραμμα για να τους ελέγξεις).Το γιατί ψάξτο λίγο μόνος σου και αν δεν εδώ είμαστε(Αν δεν το καταλάβεις δεν θα ξέρεις να απαντήσεις άμα σε ρωτήσουν στον έλεγχο)

Aκριβώς, αυτό του έγραψα και εγώ.

 

Δεν ήθελα να στείλουμε λινκς με τρέχα γύρευε αλγορίθμους σε πρωτοετή.

Αλλά αυτά που αναφέρθηκαν παραπάνω μερικά γνωρίζω, και άλλα έμαθα. Χρήσιμο!