Primtallenes fordeling på tallinja

[kyrsjo]

Jeg har skrevet et lite program som regner ut primtall (java, kildekode: se neders), og er sterkt overrasket over hvor tett de ligger spredd utover tallinja - det blir ikke eksponentiellt lenger mellom dem?!? Noen som har peiling på hvordan man kan analysere dette? Holder på å regne ut de 20 000 første primtallene bare for å teste algoritmen min - niks kø på klodrik ("stormaskin" på UiO) akkurat nå, så jeg benytter meg av det... den har stått og tygget i 16 minutter nå, og kommer nok til å holde på en stund til.

 

Kode:

/*
* Dette programmet søker etter primtall i de naturlige tallene
*
* Dato: 25 august 2005
*
* Copyright Kyrre Ness Sjøbæk 2005
* Licensed under GNU GPL version 2 or higher
*
* Revisjoner: ingen
*
*/

class Primefinder {
public static void main(String[] args) {
 System.out.println ("Primefinder initializing...");
 
 // Needed variables
 int [] primes = new int[20000];	//Somewhere to store the primes
     //Alter the number between the brackets
     //in order to set how many primes you
     //want to generate.
 primes[0] = 2;  	//Need to initialize the array a bit.
 int arraypos = 0;  //Where we currently are in the array
 boolean reallyprime = true;  //Set this to false (in loop) to indicate that
     //it's not a prime
 
 System.out.println ("Finds the first " + primes.length + " primes");
 
 //Outer search loop: run through all numbers until we have primes.length primes
 //Start at n1 = 3 as we really don't want "1" getting into the array,
 //as anything is divisible by 1. "0" is even badder. "2" is already in the array
 //so no need to recheck.
 //Need to do (primes.length -1) as the acctual write is done in arraypos++
 for (int n1 = 3; arraypos < (primes.length -1); n1++) {
 	//Inner search loop: Check if n1 is divisible with any known primes
 	//Start at the smallest ones - 50% of all numbers is divisible by
 	//2, 33% by 3 etc.
 	System.out.println ("Testing number for prime: " + n1);
 	for (int n2 = 0; n2 <= arraypos && reallyprime == true; n2++) {
   System.out.println ("\t Testing if divisable with: " + primes[n2]);
   if (n1 % primes[n2] == 0) {
   	//Divisable by primes[n2]. This is *no prime*
   	reallyprime = false;
   	
   	//Debug:
   	System.out.println ("\t\t Divisable");
   }
   else {
   	//Not divisable. migth still be a prime
   	//Is this else-clause really needed?
   	
   	//Debug:
   	System.out.println ("\t\t Not divisable");
   }
 	}
 	//Debug:
 	System.out.println ("\t reallyprime: " + reallyprime);
 	
 	//Check if it was a prime
 	if (reallyprime == true) {
   //It was. Add to list.
   arraypos++;	//(we dont want to overwrite anything)
   primes[arraypos] = n1;
   System.out.println ("!!!!!!!!!!!!Prime found: " + n1);
 	}
 	//Reset. Wash, rince, and repeat.
 	reallyprime = true;
 }
 
 //We have now (hopefully) found all the primes. Print them:
 for (int n = 0; n < primes.length; n++) {
 	System.out.println ("primes[" + n + "] = " + primes[n]);
 }
 
 //Just a bit of testing: i think the primes came a bit tigth.
 //Just testing that the algoritm/implementation acctually worked rigth...
 //Aftertought: They did not. Woho!
 boolean algorithmbug = false;
 //Outer loop: run through all primes found.
 for (int n1 = 0; n1 < primes.length; n1++){
 	System.out.println ("Now testing: " + primes[n1]);
 	//Inner loop: Try to divide every prime prime[n1] with every number that:
 	//1 <= x <= prime[n1]
 	for (int n2 = 1; n2 <= primes[n1]; n2++) {
   if (primes[n1] % n2 == 0) { //Divisable
   	System.out.println ("\t Divisable by: " + n2);
   	if (n2 == 1 || n2 == primes[n1]) {
     //no bug here, but it was easyer to test this way...
   	}
   	else {
     algorithmbug = true;
     System.out.println ("BUG BUG BUG BUG BUG BUG BUG BUG BUG BUG BUG BUG!");
   	}
   }
 	}
 }
 System.out.println ("Algorithmbug?: " + algorithmbug);
}
}

 

Har forøvrig en annen algoritme liggende, som jeg ikke har implementert ennå. Skal laste opp her ASAP når den er ferdig implementert.

 

Et tips om du ønsker å kjøre den selv: dytt outputet inn i en fil, slik:

"java Primefinder > primes.txt"

og les på det etterpå.

Kompilere:

"javac Primefinder.java"

 

Dersom du går på uio, skulle det være mulig å se på beregningsresultatet mitt - se i:

~kyrrens/java/primes.txt

Merk at jeg kommer til å slette denne rimelig snart, da fila er på litt over en GB (når den har regnet i 20 minutter...), i en profilstørrelse på 200 MB...

[kyrsjo]

Sletta gigant-filen min, og ba den lage en oversikt over de 500 første, noe som er rimelig kjappt gjort. (det tar lengre tid å regne ut etterhvert som tallene blir større - eksponentiellt...):

http://folk.uio.no/kyrrens/primes.txt

(ca 6 mb. Tar litt tid å rendre.)

 

Øverst er det en "logg" over beregningen. Deretter kommer en oversikt over alle primtallene den har funnet, og deretter en logg over testing av at algoritmen er riktig. Kosen Sich

[Snillingen]

Jeg kjønte ikke helt hva du ville med denne posten, det er sikkert fordi jeg ikke kan så mye om primtall, men kan du alikevel forklare?

[Codename_Paragon]

Først et raskt innspill før du spiser opp maskinen i CPUforbruk: skal du teste om tallet n er et primtall, trenger du ikke å teste om det lasr seg dele med tall større enn roten av n.

 

Eksempel: for å se om 37 er et primtall trenger du ikke å teste med divisor større enn 6.

 

Addendum:

Primtallsfordelinegn er en kilde til mye tenking, og den er ganske ugjevn, ikke minst fordi en stadig finner primtallspar (f.eks 29, 31 og 51,53 osv). En kan finne mange merkelige mønster, f.eks. dersom du merker av primtall i en kvadratisk spiral

7   8   9  10
6   1   2  11
5   4   3  12
16 15 14 13

Endret 26. august 2005 av Codename_Paragon

[kyrsjo]

Først et raskt innspill før du spiser opp maskinen i CPUforbruk: skal du teste om tallet n er et primtall, trenger du ikke å teste om det lasr seg dele med tall større enn roten av n.

 

Eksempel: for å se om 37 er et primtall trenger du ikke å teste med divisor større enn 6.

Jøss. Det viste jeg ikke...

*tenkeuthvorfor*

n = (sqrt(n))^2

 

(sqrt(n)+1)*z > n ?

 

Hvorfor ikke:

 

n < (n/2) * z

 

hvor z element i N (naturlige tall)

 

Snillingen:

Et primtall er et tall som bare er delelig med seg selv og 1. Eksempler er 2,3,5,7,11,13,...

f.eks. er 6 ikke et primtall fordi det er produktet av 2 og 3 (2*3=6) -altså er det delelig med 2 og 3.

 

forøvrig er *alle* tall (bortsett fra null) delelig med seg selv og 1.

[Codename_Paragon]

Først et raskt innspill før du spiser opp maskinen i CPUforbruk: skal du teste om tallet n er et primtall, trenger du ikke å teste om det lasr seg dele med tall større enn roten av n.

 

Eksempel: for å se om 37 er et primtall trenger du ikke å teste med divisor større enn 6.

Jøss. Det viste jeg ikke...

*tenkeuthvorfor*

n = (sqrt(n))^2

Jeg har begått en god del primtallssøk i mine yngre dager, dengang en måtte til med assemblyprogrammering for at det skulle bli noe dreis på sakene.

 

Årsaken til at en ikke trenger å gå høyere enn til roten av tallet en undersøker er besnærende enkelt når en tenker seg om. Dersom tallet p er delelig med a og b, betyr det at det ene taller er mindre enn roten av p og det andre må være større.

 

Hadde begge vært mindre, ville produktet vært mindre enn p

Hadde begge vært større, ville produktet vært større enn p

Dette er nok ikke helt bevisførsel "ad absurdum", men er tett opptil.

 

Edit: for å være pirkete er det et lite unntak der a=b.

Endret 27. august 2005 av Codename_Paragon

[Snillingen]

kyrsjo: det er ikke det at jeg ikke viste hva primtall var jeg lurte på hva du ville ha hjelp til og/ eller hva du ville snakke om, men takk for at du svarte

[JBlack]

Jeg vet heller ikke hva formålet med denne var, siden det finnes masse informasjon om primtall på nett. Så om kunnskap er formålet, så er det bedre å gjøre litt research.

 

Det finnes også mange algoritmer tilgjengelig, som er mye raskere enn denne.

 

Når det er sagt, så skriver du ut masse unødvendig informasjon. Og det er garantert den størte tidsspiseren i implementeringen av denne algoritmen. Pluss at all den teksten spiser HD-plass.

[ddd-king]

Jeg ser også lite nyttighet i denne posten.

Hva som er formålet med denne posten tør jeg ikke å tenke høyt, pga. faren for å bli skutt...

[kyrsjo]

Først et raskt innspill før du spiser opp maskinen i CPUforbruk: skal du teste om tallet n er et primtall, trenger du ikke å teste om det lasr seg dele med tall større enn roten av n.

 

Eksempel: for å se om 37 er et primtall trenger du ikke å teste med divisor større enn 6.

Jøss. Det viste jeg ikke...

*tenkeuthvorfor*

n = (sqrt(n))^2

Jeg har begått en god del primtallssøk i mine yngre dager, dengang en måtte til med assemblyprogrammering for at det skulle bli noe dreis på sakene.

 

Årsaken til at en ikke trenger å gå høyere enn til roten av tallet en undersøker er besnærende enkelt når en tenker seg om. Dersom tallet p er delelig med a og b, betyr det at det ene taller er mindre enn roten av p og det andre må være større.

 

Hadde begge vært mindre, ville produktet vært mindre enn p

Hadde begge vært større, ville produktet vært større enn p

Dette er nok ikke helt bevisførsel "ad absurdum", men er tett opptil.

 

Edit: for å være pirkete er det et lite unntak der a=b.

Var trøtt i går. Skjønner nå hvorfor den må være større - jeg har testet alle som er mindre, og den største mulige er derfor kvadratroten.

 

Og ja, jeg vet at utskriften er en diger tids- og HD-spiser. Men det gjør det lettere å forstå hva den faktisk gjør. Hadde tenkt å implementere en "bryter" på kommandolinja, men da må jeg først bla litt i javaboken min.

 

Aner meg nok at det finnes en hel haug mer effektive algoritmer - men halve morroa er å finne på og implementere en algoritme Å bla opp en på nettet... Vel... Det kan bestemoren din gjøre.

 

Grunnen til at jeg opprettet tråden, var det at jeg stusset over at de ikke fordelte seg med stadig økende avstand utover tallinja, men heller sprer seg jevnt. Det synes jeg er rart...

 

Hvordan jeg skulle kunne skyte ddd-king igjennom internett, er meg et mysterium. Ikke fortell hvordan du skyter folk over nettet til noen, er du snill. Ikke at jeg har noen grunn til å skyte noen. Jeg er passifist.

[Codename_Paragon]

Om jeg ikke overfortolker trådstarter, er hensikten å utforske primtallsfordelingen. Selv om primtall har pirret nysgjerrigheten til de skarpeste hoder i århundre, og ingen forventer gjennombrudd i denne tråden, synes jeg personlig at målet er er godt. Og selv om en ikke her skaper seg et navn på høyde med Gauss, Fermat og Euler, kan en likevel lære litt og sette pris på veien en går. Jeg har selv lekt litt med dette, syntes det var artig.

 

Ellers, har du sjekket Wikipedia? Jeg ser det er en rekke artikler om primtall og fordelingen av disse.

[dravisher]

Er det ikke meget tregt det programmet der da? Skjønner du fikk optimalisert litt med dele på maks sqrt(n), men likevel? 16 minutter på de 20 000 første talla hørtes lenge ut. Vi lagde et program i C++ som bare telte alle primtall fra et tall til et tall. Husker ikke eksakt hvor lang tid vi brukte på å finne alle tal fra 0 til 100000, men tror ikke det var målbart en gang. Nå skrev ikke vi tallene ut til fil, men det skal da ikke være så stor forskjell?

 

Vi fikk funnet ut antall primtall opp til rundt 4 000 000 000. Lengre gikk det ikke pga at int ikke støttet høyere tall...

[kyrsjo]

Ja utskriften er en stor hastighetssenker i dette programmet. Java en annen