Java: Primtallgenerering og -faktorisering
Hvordan kan man finne alle primtall mindre enn k? Hvordan sjekke om et gitt heltall n er primtall? Hvordan kan vi primtallsfaktorisere ethvert tall?
Først av alt må man etablere et par matematiske sannheter:
- Et primtall er et helt tall større enn 1 som bare er delelig med seg selv og med 1
- Et heltall k er også primtall dersom det ikke er delelig med andre primtall mindre enn eller lik kvadratrota til k.
- Et hvert heltall større enn 1 kan skrives som produktet av ett eller flere primtall.
Så, hvordan kan man finne et primtall?
- Gitt et heltall k, begynner vi å sjekke om tallet er delelig med det minste primtallet, 2.
- Om det er delelig, kan vi trekke konklusjonen om at tallet ikke er primtall.
- Dersom det ikke er delelig, går vi videre til 3. Dette gjentar vi for alle primtall
.
- Om ingen tall er delelige, er tallet et primtall.
Vi kan nå begynne å skrive Java-koden vår, og en kan for eksempel ende opp med noe slikt:
public boolean isPrime (int n)
{
int q = (int) Math.sqrt (n);
boolean isPrime = true;
for (int i = 2; i < q; i++)
{
if (n % i == 0)
{
return false;
}
}
return true;
}
Det første vi gjør er å ta kvadratrota til heltallet vårt. Deretter kjører vi gjennom alle heltall 
Primtallsfaktorisering
Ved aritmetikkens fundamentalteorem vet vi at et heltall større enn 1 er enten et primtall, eller et produkt av ett eller flere primtall.
For eksempel er:
public Integer[] primeFactorization (int a)
{
ArrayList factors = new ArrayList();
// fetch primes less than or equal to sqrt(a).
// if no primes are returned, the number itself is a prime.
Integer[] primes = primes ((int)Math.sqrt(a));
int i = 0;
while (i < primes.length)
{
int p = primes[i];
if (Arrays.asList (primes).contains(a) || isPrime (a))
{
// the remaining number is now a prime.
break;
}
if (a % p == 0)
{
// add the prime to our list, and execute the division
factors.add (p);
a = a / p;
}
else
{
// Continue to next prime, if the current one does not
// divide
i++;
}
}
// The number than remains should be a prime itself.
if (a > 1)
{
factors.add (a);
}
return (Integer[]) factors.toArray(new Integer[factors.size()]);
}
Her ble det kanskje litt komplisert med det første, men prosessen er igrunn ganske enkel:
- primes() til å gi oss et int-array med primtall (bruker funksjonen isPrime())
- Deretter går vi gjennom alle primtallene, og sjekker om tallet a er delelig med p. Dersom det er delelig, så legger vi primtallet p i samlingen vår og utfører divisjonen
.
- I neste runde tester vi enten det samme primtallet som i forrige runde, eller så tester vi det neste primtallet. Det er først når det gjeldende primtallet ikke er delelig, at vi går til neste.
- Til slutt skal det resterende tallet selv være et primtall, men vi ønsker ikke å inkludere tallet 1 som faktor.
Eksempel
Om vi bruker tallet 7007 om igjen, så vil vi i Java-funksjonen få følgende primtall:
Deretter tester vi først om 2 er delelig med 7007. Det er det ikke, så vi går videre til neste primtall. Det er først når vi kommer til 7 at vi finner et primtall som er delelig med 7007.
Vi legger da til tallet 7 i listen vår, og utfører divisjonen 
Når vi i påfølgende runde tester 7 igjen, finner vi ut at det ikke lengre er delelig. Men det er primtallet 11! Det siste primtallet vil da være 13.
Dette gir oss følgende i resultat: 
