[Java] Hitta primtal, addera primtal

Tycker inte du ska försöka dig på Eratostenes såll, utan köra på den enkla metoden som du redan försökt dig på även om den inte riktigt fungerar som du vill.

Oftast brukar sådana här problem klarna om man funderar igenom vad man vill göra mer precist. Som exemepl: Primtal är ju ett tal x om det inte är delbart med andra tal än sig själv och 1. Så hur kan man kolla det? Jo, om man loopar igenom alla tal mellan 1 och x och ser ifall man kan dela så borde det bli rätt (Det här har du redan tänkt ut antar jag?).
Sen kan man skissa lite:
1. x = talet att testa om det är ett primtal
2. Loopa igenom alla tal "i" mellan 1 och x
3. Om x inte är delbart med y vet vi inget mer
4. Om x är delbart med i vet vi att x inte är ett primtal, alltså kan vi bryta loopen
5. Skriv ut x ifall x är ett primtal.
Sen skissar man lite mer, fast denna gång i sitt språk, dvs java:

x = tal; // 1. bara för att göra det enkelt för mig, blir ju konstigt att prata om tal som både en variabel och som ett tal
for (i = 0; i < x; i++ ) // 2. 
{
     if (x % i != 0) // 3. den här biten var ju inte till mycket hjälp..
    {} 
    if (x % i == 0) // 4.
    {
        break; 
    }
}
// 5. Hur vet vi om loopen bröts? Det gör vi inte.

Så, då är bara frågan hur vi vid 5. ska kunna veta vad som hände vid 4.? En metod kan vara att lagra resultatet i en variabel z, tex en boolean (eller e det bool i Java?). Då kan vi i 5. kolla om z är True eller False med en if, och om den är True så skriver vi ut, annars inte.

När du löst den biten ska det såklart stoppas ihop med resten av programmet. Det klarar du nog om du förstått hur du tar fram ett primtal. Allt ska ju "bara" göras för alla tal mellan 2 och det jämna talet.

Aja, är möjligt förklaringen suger, men tyckte det var mer värt än att bara klippa in rätt kod, då jag tror att det rätta tänket är viktigast innan man hunnit få grepp om allting.

Annars kan du ju använda ett primtalstest baserat på Fermats lilla sats och randomisera basen. Då har du 50% chans att du har fel (påstår att det är ett sammansatt tal när det inte är det), så upprepar du igen med en annan bas, så har du 25% chans att du har fel, etc. Du får se upp för Carmichaeltal, men de är inte många alls så de kan du nästan bortse ifrån...

Förstår inte nyttan med att implementera en algoritm som man inte förstår hur den fungerar. Speciellt inte i en programmeringskurs.

? Jag berättade ju precis. Det är bara att kolla upp Fermats sats och använda den? Glasklar beskrivning, tycker i alla fall jag...

Kanske var lite otydligt osså smög det sig in en bug, så försöker igen med en liten förändring:

Jag pratar bara om hur man kan se om ett tal, x, är ett primtal, inte hur man kollar alla tal mindre än 10 eller nånting annat. Alltid bäst att börja i små steg..

Hur vet vi då om ett tal, x, är ett primtal? Jo, om x inte är (jämnt) delbart med något annat tal än sig själv och 1. Så det som behövs göras är att kolla igenom alla tal mellan 1 och x och se ifall man kan dela x med dom:

for (i = 2; i < x; i++ )
{   
    if (x % i == 0)
    {
        System.out.println("x var delbart med ett av talen"); 
    }
}

Men nu måste du på något vis veta om den har skrivit ut "x var delbart med ett av talen" när den kört igenom hela for-loopen, för om den har gjort det var det ju inget primtal. Men programmet kan såklart inte veta om det skrivits ut något eller ej, alltså måste vi spara det..

En variant man kan göra är att använda en boolean:
1.

boolean var_delbart = False;

2.

var_delbart=True;

3.

if (var_delbart == False)
{
   // Den här koden körs om x inte är delbart, dvs x är ett primtal.
}

1. ska vara före for-loopen.
2. sätter vi i if-satsen, vi vill ju att var_delbart ska ändra värde om x är delbart.
3. sätter vi sist, det e ju då vi vill kunna köra en viss kod om x är ett primtal

public static void main(String[] args) {
ArrayList<Integer>list= new ArrayList<Integer>();

int num = 30;

for(int i= 2; i<=num; i++){
if((i%2==0 && i/2!=1)|| (i%3==0 && i/3!=1) || (i %5==0 && i/5!=1) || (i %7==0 && i/5!=1)){
}

else{
list.add(i);
System.out.println("Prime: "+ i);
}
}

for(int i = 0; i<list.size();i++){
for(int j = 0; j<list.size();j++){
int temp = list.get(i)+list.get(j);
if(temp==num)
System.out.println(list.get(i)+ " + " +list.get(j));

}

}

public static void main(String[] args) {
ArrayList<Integer>list= new ArrayList<Integer>();

int num = 30;

for(int i= 1; i<=num; i++){
if((i%2==0 && i/2!=1)|| (i%3==0 && i/3!=1) || (i %5==0 && i/5!=1) || (i %7==0 && i/5!=1)){
}

else{
list.add(i);
System.out.print(i " , ");
}
}

for(int i = 0; i<list.size();i++){
for(int j = 0; j<list.size();j++){
int temp = list.get(i)+list.get(j);
if(temp==num)
System.out.println(list.get(i)+ " + " +list.get(j));

}

}

en väldigt lätt och smidig metod är annars att ha en vecktor som du lägger in primtal du hittar i. sen för att testa om ett tal är primtal kollar du om något tal i den vektorn delar talet. annars är det ett primtal. (behöver endast testa tills kvoten blir mindre än ett)

Detta borde ta fram alla primtal innan det tal som skrevs in:

for (int i = 2; i < tal; i++) //tal är det jämna talet du skrev
{
   for (int i1 = 2; i1 < ROTENUR(i)+1; i1++) // ROTENUR() ska bytas ut mot funktionen för roten ur...
   {
      if (i % i1 == 0)
      {
         System.out.println(i); //här borde den kriva ut alla primtal i talet
         break;
      }
   }
}

Ingen som använder Miller Rabin? Jag hade sparat de minsta primtalen i en uppslagstabell och kört Miller Rabin på resten...

Svar på din fråga.Kolla om jag har rätt på detta.
Eftersom det långa talet är udda, så måste ett av de två sökta talen vara udda och det andra jämnt. (Annars kan inte summan av dem bli udda.)

Det finns bara ett jämnt primtal: 2.

Alltså måste det ena talet vara 2 och då blir det andra talet
879976242195951958890801816612768566943805170226410617823301865416003514546684111640331356490455690766475339038983303063831818394885482954417406863802340357540397021808027209610884076158915519334125353771492979

Lite ludigt men håll till godo.

Det låter som en bra ide men av det första inlägget att döma så verkar det mer som om uppgiften går ut på att trådskaparen skall sitta och klura ut en "egen" lösning på problemet. Dock kan det ju vara bra att känna till att Miller-Rabins primtalstest finns implementerat i Java vilket verkar vara språket som används här. Spana in klassen BigInteger och då speciellt metoden isProbablePrime.

Det finns en deterministisk variant av Miller Rabin som garanterar att ett tal är eller inte är primtal. Den här är dock väldigt slö men går att modifieras att bara använda ett visst antal witnesses/baser, vilket garanterar primtal under en övre gräns. Bättre grupper av baser upptäcks kontinuerligt vilket kan ge väldigt schysst prestanda för små tal (typ < 10^16). En vettigt implementation faller tillbaka till vanliga MR ovanför den övre gränsen.

Som exempel kan nämnas att mitt Pythonprimtaltstest som använder baser som upptäcktes 2006 är snabbare än Maple 7:s isprime(), helt enkelt för att Maple 7 är äldre och detta inte var känt då.

Vägen till framgång:

1) Testa några små primtal.
2) Testa witness 2, returnera falskt om komposit
3) Testa witness 7, returnera falskt om komposit
4) Testa witness 61, returnera falskt om komposit
5) Om intal < 4759123141 är det garanterat primtal
6) Testa witness 3, returnera falskt om komposit
7) Testa witness 24251, returnera falskt om komposit
8) Om intal < 10^16 är det garanterat primtal, med undantag om det är 46856248255981
9) Testa slumpvalda baser nu när intal > 1e16.

Se http://math.crg4.com/primes.html

Som en "kul" notis är jag, vad jag vet, den första som implementerat ett test som kombinerar två tidigare kända grupper (2, 7, 61 för < 4759123141 samt 2, 3, 7, 61, 24251 för 10^16 exl undantaget) på ovanstående vis för att spara lite skön prestanda. Uppenbart, givetvis, men ändå.