David Steinsland – informatikkstudent og webutvikler

2. oktober, 2011 | Ingen kommentarer »

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:

1. Et primtall er et helt tall større enn 1 som bare er delelig med seg selv og med 1
2. Et heltall k er også primtall dersom det ikke er delelig med andre primtall mindre enn eller lik kvadratrota til k.
3. Et hvert heltall større enn 1 kan skrives som produktet av ett eller flere primtall.

Så, hvordan kan man finne et primtall?

1.  Gitt et heltall k, begynner vi å sjekke om tallet er delelig med det minste primtallet, 2.
2. Om det er delelig, kan vi trekke konklusjonen om at tallet ikke er primtall.
3. Dersom det ikke er delelig, går vi videre til 3. Dette gjentar vi for alle primtall .
4. 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 . Dersom tallet skulle være delelig med et annet, da er det ikke et primtall. Når løkken er gjennomført, vet vi at ingen tall er delelige og at heltallet vårt er primtall.

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:

1. primes() til å gi oss et int-array med primtall (bruker funksjonen isPrime())
2. 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 .
3. 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.
4. 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:

. Det er alle primtall som er mindre enn kvadratroten til 7007.

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 . I neste runde tester vi tallet 7 en gang til, og igjen så er det delelig. Vi utfører da .

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: som forteller oss hvilke primtallsfaktorer som gir 7007.