Gibt es einen einfachen Algorithmus, der feststellen kann, ob X Primzahl ist und einen bloßen sterblichen Programmierer nicht verwirren?
https://stackoverflow.com/questions/188425
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich habe versucht, mich durch Project Euler zu bearbeiten, und habe eine Handvoll Probleme bemerkt, um eine Primzahl als Teil davon zu ermitteln.
Ich weiß, dass ich X nur durch 2, 3, 4, 5, ..., Quadratwurzel von x teilen kann, und wenn ich zur Quadratwurzel komme, kann ich (sicher) annehmen, dass die Zahl Prime ist. Leider scheint diese Lösung ziemlich klunky zu sein.
Ich habe mich mit besseren Algorithmen befasst, um festzustellen, ob eine Zahl Prime ist, aber schnell verwirrt ist.
Gibt es einen einfachen Algorithmus, der feststellen kann, ob X Primzahl ist und einen bloßen sterblichen Programmierer nicht verwirren?
Vielen Dank!
Lösung
Der erste Algorithmus ist ziemlich gut und verwendet viel für Project Euler. Wenn Sie die maximale Zahl kennen, die Sie möchten, können Sie auch Eratosthenes 'Sieb recherchieren.
Wenn Sie die Liste der Primzahlen beibehalten, können Sie auch das erste Algo verfeinern, um sich nur bis zur Quadratwurzel der Zahl zu teilen.
Mit diesen beiden Algoritmen (Division und Sieb) sollten Sie in der Lage sein, die Probleme zu lösen.
Bearbeiten: behobener Name wie in Kommentaren angegeben
Andere Tipps
So generieren Sie alle Primzahlen weniger als eine Grenze Sieb von Eratosthenes (Die Seite enthält Varianten in 20 Programmiersprachen) ist die älteste und einfachste Lösung.
In Python:
def iprimes_upto(limit):
is_prime = [True] * limit
for n in range(2, limit):
if is_prime[n]:
yield n
for i in range(n*n, limit, n): # start at ``n`` squared
is_prime[i] = False
Beispiel:
>>> list(iprimes_upto(15))
[2, 3, 5, 7, 11, 13]
Ich sehe, dass Fermats Primalitätstest bereits vorgeschlagen wurde, aber ich habe durchgearbeitet Struktur und Interpretation von Computerprogrammen, und sie geben auch das Miller-Rabin-Test (Siehe Abschnitt 1.2.6, Problem 1.28) als eine andere Alternative. Ich habe es mit Erfolg für die Euler -Probleme verwendet.
Hier ist eine einfache Optimierung Ihrer Methode, die nicht ganz das Sieb von Eratosthenes ist, aber sehr einfach zu implementieren ist von 6*J-1 und 6*J+1. Dies überspringt automatisch alle Zahlen, die um 2 oder 3 teilbar sind und Ihnen eine ziemlich schöne Beschleunigung des konstanten Faktors erhalten.
Beachten Sie die folgenden Fakten (von MathSchallenge.net):
- Alle Primzahlen außer 2 sind ungerade.
- Alle Primzahlen größer als 3 können in Form 6K - 1 oder 6K + 1 geschrieben werden.
- Sie müssen nicht die Quadratwurzel von N überprüften
Hier ist die C ++ - Funktion, die ich für relativ kleines N verwende:
bool isPrime(unsigned long n)
{
if (n == 1) return false; // 1 is not prime
if (n < 4) return true; // 2 and 3 are both prime
if ((n % 2) == 0) return false; // exclude even numbers
if (n < 9) return true; //we have already excluded 4, 6, and 8.
if ((n % 3) == 0) return false; // exclude remaining multiples of 3
unsigned long r = floor( sqrt(n) );
unsigned long f = 5;
while (f <= r)
{
if ((n % f) == 0) return false;
if ((n % (f + 2)) == 0) return false;
f = f + 6;
}
return true; // (in all other cases)
}
Sie könnten sich wahrscheinlich an eigene Optimierungen vorstellen.
Ich würde empfehlen Fermats Primalitätstest. Es ist ein probabilistischer Test, aber überraschend oft korrekt. Und es ist unglaublich schnell im Vergleich zum Sieb.
Für einigermaßen kleiner Zahlen ist x%n für bis zu SQRT (x) schrecklich schnell und einfach zu codieren.
Einfache Verbesserungen:
Nur Test 2 und ungerade Zahlen.
Test 2, 3 und Vielfachen von 6 + oder - 1 (alle anderen Primzahlen als 2 oder 3 sind ein Vielfaches von 6 +/- 1.
Testen Sie nur Primzahlen (müssen alle Primzahlen bis SQRT (x) berechnen oder speichern).
Sie können die Siebmethode verwenden, um schnell eine Liste aller Primzahlen bis zu einer willkürlichen Grenze zu generieren, ist jedoch in der Regel Speicherintensiv. Sie können die Vielfachen von 6 Tricks verwenden, um die Speicherverwendung auf 1/3 von etwas pro Zahl zu reduzieren.
Ich habe eine einfache Prime-Klasse (C#) geschrieben, die zwei Bitfields für Vielfachen von 6+1 und Multiples von 6-1 verwendet, und dann eine einfache Suche ... und wenn die Nummer, die ich teste, außerhalb der Grenzen des Siebs liegt, Dann fällt es beim Testen mit 2, 3 und Multiples von 6 +/- Kuss Prinzip erneut schlägt wieder!
Ich schrieb eine Prime-Klasse, die ein Sieb verwendet, um kleinere Primzahlen vorzubereiten, und stützt sich dann auf das Testen mit 2, 3 und Vielfachen von sechs +/- 1 für diejenigen außerhalb des Siebs.
Für Project Euler ist es wirklich wichtig, eine Liste von Primzahlen zu haben. Ich würde vorschlagen, eine Liste beizubehalten, die Sie für jedes Problem verwenden.
Ich denke, was Sie suchen, ist das Sieb von Eratosthenes.
Ihr Recht, die Simples sind am langsamsten. Sie können es etwas optimieren.
Schauen Sie sich den Modul anstelle von quadratischen Wurzeln an. Behalten Sie Ihre Primzahlen im Auge. Sie müssen nur 7 durch 2, 3 und 5 teilen, da 6 ein Vielfaches von 2 und 3 ist und 4 ein Vielfaches von 2 ist.
Rslite erwähnte die Eranthenos Sieb. Es ist ziemlich einfach. Ich habe es in mehreren Sprachen es nach Hause. Fügen Sie einen Kommentar hinzu, wenn Sie diesen Code später posten sollen.
Hier ist mein C ++ eins. Es hat viel Raum, um sich zu verbessern, aber es ist schnell im Vergleich zu den dynamischen Sprachenversionen.
// Author: James J. Carman
// Project: Sieve of Eratosthenes
// Description: I take an array of 2 ... max values. Instead of removeing the non prime numbers,
// I mark them as 0, and ignoring them.
// More info: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
#include <iostream>
int main(void) {
// using unsigned short.
// maximum value is around 65000
const unsigned short max = 50000;
unsigned short x[max];
for(unsigned short i = 0; i < max; i++)
x[i] = i + 2;
for(unsigned short outer = 0; outer < max; outer++) {
if( x[outer] == 0)
continue;
unsigned short item = x[outer];
for(unsigned short multiplier = 2; (multiplier * item) < x[max - 1]; multiplier++) {
unsigned int searchvalue = item * multiplier;
unsigned int maxValue = max + 1;
for( unsigned short maxIndex = max - 1; maxIndex > 0; maxIndex--) {
if(x[maxIndex] != 0) {
maxValue = x[maxIndex];
break;
}
}
for(unsigned short searchindex = multiplier; searchindex < max; searchindex++) {
if( searchvalue > maxValue )
break;
if( x[searchindex] == searchvalue ) {
x[searchindex] = 0;
break;
}
}
}
}
for(unsigned short printindex = 0; printindex < max; printindex++) {
if(x[printindex] != 0)
std::cout << x[printindex] << "\t";
}
return 0;
}
Ich werde den Perl- und Python -Code aufwerfen, den ich habe, sobald ich ihn finde. Sie sind ähnlich im Stil, nur weniger Linien.
Hier ist ein einfacher Primalitätstest in D (Digital Mars):
/**
* to compile:
* $ dmd -run prime_trial.d
* to optimize:
* $ dmd -O -inline -release prime_trial.d
*/
module prime_trial;
import std.conv : to;
import std.stdio : w = writeln;
/// Adapted from: http://www.devx.com/vb2themax/Tip/19051
bool
isprime(Integer)(in Integer number)
{
/* manually test 1, 2, 3 and multiples of 2 and 3 */
if (number == 2 || number == 3)
return true;
else if (number < 2 || number % 2 == 0 || number % 3 == 0)
return false;
/* we can now avoid to consider multiples
* of 2 and 3. This can be done really simply
* by starting at 5 and incrementing by 2 and 4
* alternatively, that is:
* 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, ...
* we don't need to go higher than the square root of the number */
for (Integer divisor = 5, increment = 2; divisor*divisor <= number;
divisor += increment, increment = 6 - increment)
if (number % divisor == 0)
return false;
return true; // if we get here, the number is prime
}
/// print all prime numbers less then a given limit
void main(char[][] args)
{
const limit = (args.length == 2) ? to!(uint)(args[1]) : 100;
for (uint i = 0; i < limit; ++i)
if (isprime(i))
w(i);
}
Ich arbeite auch durch die Projekte für Projekte und habe in der Tat nur die Nummer 3 (nach ID) beendet. Dies ist die Suche nach dem höchsten Prime -Faktor einer zusammengesetzten Zahl (die Zahl in der? 600851475143).
Ich habe mir alle Informationen zu Primzahlen (die hier bereits erwähnten Siebtechniken) und über die ganzzahlige Faktorisierung von Wikipedia angesehen und einen Algorithmus zur Abteilung von Brute Force -Versuchsabteilung entwickelt, den ich entschieden habe.
Während ich die Euler -Probleme mache, um Ruby zu lernen Hauptklasse und ein Ganzzahlklasse mit einer Prime_division Methode. Wie cool ist das. Ich konnte die richtige Antwort auf das Problem mit diesem Ruby -Snippet erhalten:
require "mathn.rb"
puts 600851475143.prime_division.last.first
Dieser Snippet gibt die richtige Antwort auf die Konsole aus. Natürlich habe ich eine Menge Lesen und Lernen gemacht, bevor ich auf diese kleine Schönheit gestoßen bin. Ich dachte nur, ich würde sie mit allen teilen ...
Ich mag diesen Python -Code.
def primes(limit) :
limit += 1
x = range(limit)
for i in xrange(2,limit) :
if x[i] == i:
x[i] = 1
for j in xrange(i*i, limit, i) :
x[j] = i
return [j for j in xrange(2, limit) if x[j] == 1]
Eine Variante davon kann verwendet werden, um die Faktoren einer Zahl zu generieren.
def factors(limit) :
limit += 1
x = range(limit)
for i in xrange(2,limit) :
if x[i] == i:
x[i] = 1
for j in xrange(i*i, limit, i) :
x[j] = i
result = []
y = limit-1
while x[y] != 1 :
divisor = x[y]
result.append(divisor)
y /= divisor
result.append(y)
return result
Wenn ich eine Reihe von Zahlen berücksichtigt hätte, würde ich natürlich den Cache nicht neu berechnen; Ich würde es einmal machen und darin nachgehen.
Ist nicht optimiert, aber es ist eine sehr einfache Funktion.
function isprime(number){
if (number == 1)
return false;
var times = 0;
for (var i = 1; i <= number; i++){
if(number % i == 0){
times ++;
}
}
if (times > 2){
return false;
}
return true;
}
Vielleicht kann diese Implementierung in Java hilfreich sein:
public class SieveOfEratosthenes {
/**
* Calling this method with argument 7 will return: true true false false true false true false
* which must be interpreted as : 0 is NOT prime, 1 is NOT prime, 2 IS prime, 3 IS prime, 4 is NOT prime
* 5 is prime, 6 is NOT prime, 7 is prime.
* Caller may either revert the array for easier reading, count the number of primes or extract the prime values
* by looping.
* @param upTo Find prime numbers up to this value. Must be a positive integer.
* @return a boolean array where index represents the integer value and value at index returns
* if the number is NOT prime or not.
*/
public static boolean[] isIndexNotPrime(int upTo) {
if (upTo < 2) {
return new boolean[0];
}
// 0-index array, upper limit must be upTo + 1
final boolean[] isIndexNotPrime = new boolean[upTo + 1];
isIndexNotPrime[0] = true; // 0 is not a prime number.
isIndexNotPrime[1] = true; // 1 is not a prime number.
// Find all non primes starting from 2 by finding 2 * 2, 2 * 3, 2 * 4 until 2 * multiplier > isIndexNotPrime.len
// Find next by 3 * 3 (since 2 * 3 was found before), 3 * 4, 3 * 5 until 3 * multiplier > isIndexNotPrime.len
// Move to 4, since isIndexNotPrime[4] is already True (not prime) no need to loop..
// Move to 5, 5 * 5, (2 * 5 and 3 * 5 was already set to True..) until 5 * multiplier > isIndexNotPrime.len
// Repeat process until i * i > isIndexNotPrime.len.
// Assume we are looking up to 100. Break once you reach 11 since 11 * 11 == 121 and we are not interested in
// primes above 121..
for (int i = 2; i < isIndexNotPrime.length; i++) {
if (i * i >= isIndexNotPrime.length) {
break;
}
if (isIndexNotPrime[i]) {
continue;
}
int multiplier = i;
while (i * multiplier < isIndexNotPrime.length) {
isIndexNotPrime[i * multiplier] = true;
multiplier++;
}
}
return isIndexNotPrime;
}
public static void main(String[] args) {
final boolean[] indexNotPrime = SieveOfEratosthenes.isIndexNotPrime(7);
assert !indexNotPrime[2]; // Not (not prime)
assert !indexNotPrime[3]; // Not (not prime)
assert indexNotPrime[4]; // (not prime)
assert !indexNotPrime[5]; // Not (not prime)
assert indexNotPrime[6]; // (not prime)
assert !indexNotPrime[7]; // Not (not prime)
}
}
Der AKS Prime Testing Algorithmus:
Input: Integer n > 1
if (n is has the form ab with b > 1) then output COMPOSITE
r := 2
while (r < n) {
if (gcd(n,r) is not 1) then output COMPOSITE
if (r is prime greater than 2) then {
let q be the largest factor of r-1
if (q > 4sqrt(r)log n) and (n(r-1)/q is not 1 (mod r)) then break
}
r := r+1
}
for a = 1 to 2sqrt(r)log n {
if ( (x-a)n is not (xn-a) (mod xr-1,n) ) then output COMPOSITE
}
output PRIME;
Ein anderer Weg in Python ist:
import math
def main():
count = 1
while True:
isprime = True
for x in range(2, int(math.sqrt(count) + 1)):
if count % x == 0:
isprime = False
break
if isprime:
print count
count += 2
if __name__ == '__main__':
main()
