[Excel]Priemgetallen aantonen en ontbinden

[Verwijderd]

Ik ben momenteel met Excel aan 't spelen om een algoritme te verzinnen waarmee ik van een getal in bijvoorbeeld veld A1 kan bepalen of het priem is of niet. Zo ja, moet dit in factoren worden ontbonden.

Even voor de goede orde: een priemgetal is dus een positieve integer dat enkel door zichzelf en door 1 gedeeld kan worden.
Voorbeelden van de eerste priemgetallen: 2, 3, 5, 7, 11, 13, 17, ...
Alle even getallen >2 vallen automatisch af, omdat deze door 2 deelbaar zijn.
Ook alle getallen die op 5 eindigen (afgezien van 5 zelf) vallen af, want ze zijn deelbaar door 5.

Ik heb al ingevoerd hoe ik de bovengenoemde niet-priemgetallen af laat vallen, maar nu moet ik dus voor alle overgebleven 'mogelijke' priemgetallen uitzoeken of ze positieve integers als deler hebben.

Nu had ik het volgende verzonnen, maar de grote vraag is: kan ik het met Excel doen?

IF(INT(A1:(1+Z))=(A1:(1+Z));"Priemgetal";"Geen priemgetal")

Z mag alleen bestaan op [1,sqrt(A1-1)], om het aantal keren 'proberen' zo klein mogelijk te houden.

Is er iemand die misschien weet hoe ik Excel alle getallen op het genoemde domein uit kan laten proberen?

Je zult vast denken: dit is toch vrij simpel te doen in VB(A)? Klopt, ik had al het volgende functietje gevonden op usenet:

code:

Function prime(num)
    Dim j, k, remain As Integer
    j = Int(num)
    If j <> num Then
    prime = "NonInt"
    Exit Function
    End If
    j = Sqr(num)
    For k = 2 To j
     remain = num Mod k
     If remain = 0 Then
      prime = "NonPrime"
      Exit Function
     End If
    Next k
    prime = "Prime"
End Function

...maar aangezien mijn kennis op het gebied van echt programmeren zeer dicht bij 0 ligt, doe ik het liever in Excel, wat ik wel min of meer beheers.

Alvast bedankt!

[VROEM!]

Alle priemgetallen schijnen op de lijn 6X +/- 1 te liggen. X is dan een integer.

Wie weet kun je daar ook wat mee. Het scheelt namelijk al enorm in hoeveel getallen je na moet kijken.

Voor de rest kan ik je niet helpen denk ik.

[Verwijderd]

Mag ik vragen hoe je daar aan komt?
Ik heb de laatste tijd behoorlijk wat theorieën gelezen, waarvan ik het grootste gedeelte overigens niet snap met m'n 5VWO WiB1,2 , maar die kende ik nog niet.

De manier die ik noemde is de manier van 'uitproberen', afgeleid van de Zeef van Eratosthenes...

[DroogKloot]

Die 6X - 1 formule werkt inderdaad, en heeft als voordeel dat het een erg snelle methode is. Maar voor het aantonen van 'priemheid' van een willekeurig getal is het niet echt een handige... beter is m.i. het volgende algorithme (pseudo-code):

code:

i = 2
while ( i < getal ) {    
  if (( getal \\ 2 ) && ( getal \\ 5)) {
    if ( getal / i == integer ) {
    return false
    }
    i++
  }
}
return true

[Verwijderd]

Jullie hebben inderdaad gelijk, dat verklaart natuurlijk ook waarom sommige van 'the world's largest primes' <onmenselijk groot getal>±1 zijn.

Die 6 komt vast omdat dat het eerste perfecte getal is (1+2+3), nu nog een mooi weggetje naar dit verband maken...

Hier kan ik zeker wat mee, alleen zie ik niet precies waarom de methode niet handig is om 'priemheid' te bepalen.

Volgens mij is het gewoon dit in Excel:
=IF(OR(((A1-1)/6)=INT((A1-1)/6);((A1+1)/6)=INT((A1+1)/6));"Het getal is priem";"Het getal is niet priem")
Dit werkt btw alleen voor getallen >7, maar daar kun je gewoon simpel een uitzondering voor maken door IF(A1<7...blabla in te voeren.

Alleen wat trickier lijkt 't mij om nu te ontbinden in factoren. Eerst maar eens maffen

[Verwijderd]

Op donderdag 15 november 2001 23:40 schreef Silacoid het volgende:
Alleen wat trickier lijkt 't mij om nu te ontbinden in factoren. Eerst maar eens maffen

uhm.. wou je de priemgetallen gaan ontbinden ?
(lijkt me niet.. aangezien je 1 en het priemgetal zelf je wortels zijn..)

en het onhandige aan bovengenoemde code is dat ie per getal, kijkt naar elk getal eronder of het een deler is.

voor priemgetal 5 zou die dus checken of, 2,3 en 4 delers zijn van 5.
kan je nagaan wat dat wordt als je een getal neemt in de orde van 10^12.

misschien heb je wat aan het bewijs dat er oneindig veel priemgetallen zijn.. (je ziet maar

de stelling is:
neem alle bekende priemgetallen, vermenigvuldig deze met elkaar. en tel 1 hier bij op. dit levert een nieuw priemgetal.

reden: als het nieuwe getal geen priemgetal zou zijn, dan zou je het moeten kunnen delen door een priemgetal.
maar omdat je net met dat priem getal hebt vermenigvuldigt, kan je die gewoon wegstrepen. (beide kanten door hetzelfde delen..) dit zou je net zo lang kunnen doen totdat je 2 priemgetallen over houdt waaruit je nieuwe getal dus bestaat. maar dat houdt in dat het getal 1 wat je erbij op hebt geteld deelbaar moet zijn door een priemgetal. en dat is dus niet zo. DUS het nieuwe getal is een priemgetal.
(het kan zijn dat het bewijs niet helemaal wiskundig correct is.. maar het lijkt er iig op. de stelling klopt wel.)

[Verwijderd]

Op vrijdag 16 november 2001 00:05 schreef Lamp het volgende:

[..]

uhm.. wou je de priemgetallen gaan ontbinden ?
(lijkt me niet.. aangezien je 1 en het priemgetal zelf je wortels zijn..)

Nee joh, alleen ontbinden als de uitkomst FALSE (Geen priem) is, want alleen dan kun je in integers ontbinden.

en het onhandige aan bovengenoemde code is dat ie per getal, kijkt naar elk getal eronder of het een deler is.

voor priemgetal 5 zou die dus checken of, 2,3 en 4 delers zijn van 5.
kan je nagaan wat dat wordt als je een getal neemt in de orde van 10^12.

Als je hier de functie uit de beginpost bedoelt, heb je helemaal gelijk. Dat is ook de reden waarom de Zeef alleen voor kleine getallen gebruikt kan worden.

De tweede code is al wat efficienter. Alleen wel jammer dat het laatste cijfer niet langer significant wordt bevonden door Excel als A1>1,0·10¹⁴-1. Dat is ook meteen het grootste getal dat ingevoerd kan worden om 'priemheid' te berekenen.

misschien heb je wat aan het bewijs dat er oneindig veel priemgetallen zijn.. (je ziet maar

de stelling is:
neem alle bekende priemgetallen, vermenigvuldig deze met elkaar. en tel 1 hier bij op. dit levert een nieuw priemgetal.

reden: als het nieuwe getal geen priemgetal zou zijn, dan zou je het moeten kunnen delen door een priemgetal.
maar omdat je net met dat priem getal hebt vermenigvuldigt, kan je die gewoon wegstrepen. (beide kanten door hetzelfde delen..) dit zou je net zo lang kunnen doen totdat je 2 priemgetallen over houdt waaruit je nieuwe getal dus bestaat. maar dat houdt in dat het getal 1 wat je erbij op hebt geteld deelbaar moet zijn door een priemgetal. en dat is dus niet zo. DUS het nieuwe getal is een priemgetal.
(het kan zijn dat het bewijs niet helemaal wiskundig correct is.. maar het lijkt er iig op. de stelling klopt wel.)

Hmm die laatste moet ik morgen maar 'ns voor mezelf uitschrijven, want zo zie ik 't nog niet direct. Je zult overigens wel gelijk hebben.
Erg bedankt voor je reactie!

[DroogKloot]

BTW,

code:

if (( (X + 1) / 6 == int ) || ( (X - 1) / 6 == int ))
  return true
}
return false

werkt ook (voor X > 5), en is sneller in de meeste talen.

[Juup]

De methode die jullie beschrijven om te bepalen of het een priem is scaled lineair met A1. Er bestaan ook methoden die wat vriendelijker scalen, en die ook een grote mate van zekerheid geven (geen volledige zekerheid). Als je bijvoorbeeld getallen in de grotteorde van 10^6 of 10^9 op primeheid wilt testen, vergeet dan bovenstaande methode en kijk naar de maurer methode.

[VROEM!]

Op donderdag 15 november 2001 21:48 schreef Silacoid het volgende:
Mag ik vragen hoe je daar aan komt?
Ik heb de laatste tijd behoorlijk wat theorieën gelezen, waarvan ik het grootste gedeelte overigens niet snap met m'n 5VWO WiB1,2 , maar die kende ik nog niet.

De manier die ik noemde is de manier van 'uitproberen', afgeleid van de Zeef van Eratosthenes...

Een leraar van me bij WB heeft ooit met zijn groep gekeken hoe ze zo snel mogelijk 100.000 priemgetallen konden berekenen in machinetaal. (Dit was in de tijd van de XT)
Dit algorithme bleek het snelst te werken voor het strepen van 'zeker geen priem' getallen.
In die tijd waren processoren nog niet zo snel, dus je moest in een regelkring echt CPU-cycle efficient proggen, dus geen delingen en vermenigvuldigingen uitvoeren en nog veel meer truukjes. Als vingeroefening daarvoor hebben ze drie maanden gewerkt aan een programma om priemen uit te rekenen.
Tegenwoordig is CPU-efficient proggen niet zo heel relevant meer voor regelaars, omdat processoren toch snel zat zijn, helemaal als je in machinetaal gaat programmeren.

[Wokker]

Ff een vraagje tussend oor door een beginner
Wat is een algo ritme ??

[VROEM!]

Een standaard manier om een hele reeks dingen op iets te controleren.

Je kunt het vergelijken met lopende band werk in de augurkenfabriek.
Er komt een pot voorbij, je kijkt of er augurken boven de rand uit steken.
Ja=>klap met de rubber hamer en probleem gefikst
Nee=> niks doen
Volgende pot.

Maar dan algemeen.

De ABC formule op alle tweedegraads vergelijkingen toepassen om ze op te lossen is bijvoorbeeld ook een algorithme.

[Tsjipmanz]

Op vrijdag 16 november 2001 09:56 schreef Wokker het volgende:
Ff een vraagje tussend oor door een beginner
Wat is een algo ritme ??

Een algoritme is een stapsgewijze oplossing voor een probleem of een taak. In principe is het recept voor het bakken van een taart ook een algoritme, omdat het stapsgewijs beschrijft wat je moet doen om een taart als eindresultaat te krijgen.

[Verwijderd]

Op vrijdag 16 november 2001 09:23 schreef Jaaap het volgende:
De methode die jullie beschrijven om te bepalen of het een priem is scaled lineair met A1. Er bestaan ook methoden die wat vriendelijker scalen, en die ook een grote mate van zekerheid geven (geen volledige zekerheid). Als je bijvoorbeeld getallen in de grotteorde van 10^6 of 10^9 op primeheid wilt testen, vergeet dan bovenstaande methode en kijk naar de maurer methode.

Wat wordt er precies onder scaled linear of scalen verstaan?

Verder: bedankt voor je antwoord, ik zal eens ff zoeken op de maurer methode.

Hier tot nu toe een PSD-tje van 't huidige algoritmetje:


Misschien kan de topictitle beter naar [Excel]Priemgetallen aantonen en ontbinden renamed worden...

[Edit: Dankq!]

[Varienaja]

Zoek je nog een algoritme om een getal te ontbinden in z'n priemfactoren? Ik had deze nog liggen:

code:

function IsPriem(n:integer):boolean;
{Test of n een priemgetal is}
var Totaan,i:integer;
begin
   if n<=3 then begin
    Result:=True;
   end else begin
    Totaan:=Trunc(Sqrt(n))+1;
    Result:=(n mod 2)<>0;
    i:=3;
    while Result and (i<=Totaan) do begin
       Result:=(n mod i)<>0;
       inc(i,2);
    end;
   end;
end;

function NextPriem(n:integer):integer;
{Levert het eerstvolgende priemgetal na n op}
begin
   if n=1 then begin
    Result:=2;
   end else begin
    Result:=n;
    if (Result mod 2)=0 then inc(Result) else inc(Result,2);
    while not IsPriem(Result) do begin
       inc(Result,2);
    end;
   end;
end;

function OntbindInPriemgetallen(n:integer):string;
{ Levert op:
  De priemgetallen waaruit n is opgebouwd volgens
  de volgende formule:
  n=p1^s1*p2^s2*...*pr^sr
  op de volgende wijze: 'p1,p2,...,pr,'}
var i,Totaan:integer;
begin
   i:=1;
   Totaan:=Trunc(Sqrt(n))+1;
   while i<Totaan do begin
    i:=NextPriem(i);
    if (n mod i)=0 then begin
       Result:=Result+IntToStr(i)+',';
    end;
   end;
end;

Ja, natuurlijk had dit efficienter gekund

[Verwijderd]

Mijn algoritme klopt helemaal niet.
6x±1 is helemaal niet betrouwbaar om te controleren of een getal priem is of niet.

Voorbeeld: 77-> 77+1=78 -> 78/6=13 -> 13=INT(13) -> 77 is priem.
Dat klopt helemaal niet, want 77/11=INT(77/11)

Shit...

[Varienaja]

Op zondag 18 november 2001 15:24 schreef Silacoid het volgende:
Mijn algoritme klopt helemaal niet.
6x±1 is helemaal niet betrouwbaar om te controleren of een getal priem is of niet.

Dacht je dat dan? Als dat zo was, dan was er ook niemand op zoek naar van die hele grote priemgetallen.

Dan deed je gewoon 6*(heel vreselijk groot getal) ± 1.

Nephilin schreef het volgende:
Die 6X - 1 formule werkt inderdaad, en heeft als voordeel dat het een erg snelle methode is. Maar voor het aantonen van 'priemheid' van een willekeurig getal is het niet echt een handige...

Zeg maar gerust inadequaat dus

[Verwijderd]

Op vrijdag 16 november 2001 09:56 schreef Wokker het volgende:
Ff een vraagje tussend oor door een beginner
Wat is een algo ritme ??

An algorithm is an ordered set of unambiguous, executable steps, defining a terminating process.


Dat is de officiele defenitie.

[Verwijderd]

Ik ga 't maar eens in de richting van Fermat zoeken.

[Verwijderd]

Op donderdag 15 november 2001 21:34 schreef VROEM! het volgende:
Alle priemgetallen schijnen op de lijn 6X +/- 1 te liggen. X is dan een integer.

[..]

Als dit al waar is (en ik geloof er niet zo erg in) betekend het nog niet dat alle getallen die op die lijnen liggen ook priem zijn, zoals sommige mensen hier wel dachten. Graag zou ik een bewijs zien van deze stelling, of een link die zelfs maar melding maakt van de stelling zelf.

Over priem testen.
Als je geen 100% zekerheid hoeft te hebben over het priem zijn van een getal kun je eens naar het volgende kijken:

Als een een getal n priem is dan geldt:

a^(n-1) mod n = 1 voor 1 <= a <= n-1

dus als 2^(n-1) mod n <> 1 dan is n zeker NIET priem.
Als 2^(n-1) mod n = 1 betekent dat echter nog niet dat n zeker WEL priem is.

Een getal dat niet priem is, maar waarvoor wel geldt dat a^(n-1) mod n = 1 noemt men een basis-a pseudopriem. Er zijn slechts 22 getallen kleiner dan 10000 die basis-2 pseudopriem zijn. Hoe groter het getal, hoe kleiner de kans dat het een pseudopriem is. Zo is de kans dat een random getal van 512 bits dat niet priem is, maar waarvoor wel geldt dat 2^(n-1) mod n = 1 kleiner dan 1 in 10^20

Nog (veel) meer zekerheid biedt de Miller-Rabin test. Maar de enige test die 100% zekerheid biedt is voor zover ik weet de bruteforce methode van door alle priems kleiner dan de wortel van het getal delen.

[Verwijderd]

Op maandag 19 november 2001 22:00 schreef Xalista een handige tip

Dat is dus Fermat's (Little) Theorem, waar ik het 1 post eerder over had

[Verwijderd]

Op maandag 19 november 2001 22:43 schreef Silacoid het volgende:

[..]

Dat is dus Fermat's (Little) Theorem, waar ik het 1 post eerder over had

Idd.

Als je hier echt mee aan de gang gaat heb je vast een modular exponentiation algoritme nodig (a^b mod n) en laat ik nou net zo'n algoritme gepost hebben in de thread "[VB6] hoe kan dit sneller gedaan worden?"

[Verwijderd]

dat truuckje kende ik inderdaad, maar ik zal eens ff kijken in die thread...

thx!

[DroogKloot]

Hmm, this seems as good a place as any... nu we het toch over modulair rekenen hebben.

Ik zit met een irritant wiskundig vraagstuk. Here goes:

a mod b = c ; c = a - (INT(a / b) * b)

a = c + (INT(a / b) * b) ; b = (a - c) / INT(a / b)

(a * x) mod (b * x) = (c * x)
(a / x) mod (b / x) = (c / x) (mits a / x en b / x integer)

Nu wil ik weten hoe c verandert als alleen a met x wordt vermenigvuldigd / door x wordt gedeeld. Beter nog: voor welke x geldt dat a mod b = c = (a / x) mod b?

Het probleem is namelijk dat a in mijn programma een onhebbelijk groot getal is (zoiets als 84^137), waar m'n arme compiler nix mee kan (en dus maar overgaat tot wetenschappelijke notatie ), en m'n algorithme daardoor totale onzin returned.

[Verwijderd]

Op dinsdag 20 november 2001 01:55 schreef Nephilin het volgende:

[..]

Nu wil ik weten hoe c verandert als alleen a met x wordt vermenigvuldigd / door x wordt gedeeld. Beter nog: voor welke x geldt dat a mod b = c = (a / x) mod b?

Het probleem is namelijk dat a in mijn programma een onhebbelijk groot getal is (zoiets als 84^137), waar m'n arme compiler nix mee kan (en dus maar overgaat tot wetenschappelijke notatie ), en m'n algorithme daardoor totale onzin returned.

Volgens mij kun je daar geen goed antwoord op geven zonder a mod b eerst uit te rekenen, en dat wil je juist voorkomen. Maar misschien heb je hier iets aan:

a mod b = x (a/x mod b) mod b, voor elk x|a (elk x die een deler is van a).

edit:

Verder distribueert de mod (volgens mij (tm)) gewoon over de vermenigvuldiging dus:

a*b mod n = (a mod n) * (b mod n) mod n

Als ik goed begrijp wat je aan het doen bent heb ik nog iets véééél beters voor je. Ben je aan het proberen om a^b mod n uit te rekenen, waarbij a^b te groot is?

Zo ja, dan word jij ook helemaal blij van het PowerMod algoritme dat ik in de thread "[VB6] hoe kan dit sneller gedaan worden?" heb gepost.

[DroogKloot]

Ben je aan het proberen om a^b mod n uit te rekenen, waarbij a^b te groot is?

Inderdaad. Ik word overigens wel blij van je tweede algorithme, maar niet helemaal lyrisch... want het geval returned een foute uitkomst

code:

  C = M    //* M is het grondtal A *//
  while ( E > 1 ) {    //* E is de exponent B *//
    if ( E mod 2 == 1 ) {
    C = (C * M) mod N
    E = E - 1
    }
    C = (C * C) mod N
    E = (E / 2)
  }
  return C

Neem ik voor A (=M) 84, voor B (=E) 137, en voor N 221, dan komt er 120 uit rollen; dit zou 67 moeten zijn... grmbl.

[Verwijderd]

euh,....je hebt gelijk.

Er wordt aan gewerkt.

[Verwijderd]

Hier heb je een nieuwe versie. Ik hoop dat nu wel helemaal lyrisch wordt.

code:

function PowerMod(a, b, n: int64): int64;
var d: int64;
    e: int64;
begin
  d := a;
  e := 1;

  while b > 1 do
  begin
    if (b mod 2) = 1 then
    begin
    e := (d * e) mod n;
    b := b - 1;
    end;
    d := (d * d) mod n;
    b := b div 2;
  end;

  result := (d * e) mod n;
end;

[DroogKloot]

Bovenstaande routine werkt, bedankt Denk dat ik dat boek over algorithmes ook maar ga aanschaffen...