Archief - [ALG] Is Priemgetal?

Het archief is een bevroren moment uit een vorige versie van dit forum, met andere regels en andere bazen. Deze posts weerspiegelen op geen enkele manier onze huidige ideeën, waarden of wereldbeelden en zijn op sommige plaatsen gecensureerd wegens ontoelaatbaar. Veel zijn in een andere tijdsgeest gemaakt, al dan niet ironisch - zoals in het ironische subforum Off-Topic - en zouden op dit moment niet meer gepost (mogen) worden. Toch bieden we dit archief nog graag aan als informatiedatabank en naslagwerk. Lees er hier meer over of start een gesprek met anderen.
T

TiZon

Legacy Member
Hey,

Hoe controleer je of een getal een priemgetal is?

Ik heb al wat met google rond gezocht, maar ik kom veel oplossingen uit, maar volgens mij zijn ze niet allemaal even juist.

Hoe zou je dit dus moeten doen?

Bedankt!
Bart
C

Cycloon

Legacy Member
Simpelste manier: Ga alle getallen af die kleiner zijn dan de helft van uw getal en kijk of de rest bij deling verschillend is van 0. Als alle getallen (excl. 1) een rest geven > 0 dan is uw getal een priemgetal.

Als ge meer en betere algoritmes wilt die sneller werken dan zijn er altijd uitzonderingen van getallen die niet kunnen gedecteerd worden met die methode. Dan zou je al verschillende combinaties moeten maken.
V

Vich

Legacy Member
Er is geen universele methode, er zijn alleen semi-brute-force manieren om te kijken of het een priemgetal is. De snelste manier is om een hele lijst uit te rekenen(of te downloaden) en te kijken of je getal erin zit.
k

killgore

Legacy Member
Cyc1oon zei:
Simpelste manier: Ga alle getallen af die kleiner zijn dan de helft van uw getal en kijk of de rest bij deling verschillend is van 0. Als alle getallen (excl. 1) een rest geven > 0 dan is uw getal een priemgetal.

Als ge meer en betere algoritmes wilt die sneller werken dan zijn er altijd uitzonderingen van getallen die niet kunnen gedecteerd worden met die methode. Dan zou je al verschillende combinaties moeten maken.
Klik om te vergroten...

je moet maar tot de vierkantswortel van je eigen getal gaan.

En vroegere priemgetallen bufferen en kijken of het daardoor deelbaar is :) (pak priem 2, dan moet je niet meer alle testen voor /4,/6,/8,... uitvoeren).
Vich zei:
Er is geen universele methode, er zijn alleen semi-brute-force manieren om te kijken of het een priemgetal is. De snelste manier is om een hele lijst uit te rekenen(of te downloaden) en te kijken of je getal erin zit.
Klik om te vergroten...

Dat is niet waar. Er zijn geoptimaliseerde technieken (zeefmethode of zo) die het berekenen wat sneller laten gaan.
Er is echter (nog) geen formule om bv. gegeven priemgetal n, priemgetal n+1 te verkrijgen.
M

Mithrandix

Legacy Member
ik zou het zo doen in java:

Code: 
import java.io.*;

public class DriverPriemGetal {
	
	public static void main (String [] args){
		int x = 0;
		try {
			BufferedReader in = new BufferedReader (new InputStreamReader(System.in));
			System.out.println("Geef getal:");
			String input = in.readLine();
			int getal = Integer.parseInt(input);
			for(int i = 1; i<getal; i++){
				if(getal%i==0){
					x++;
				}
			}
			if(x < 2 && x > 0){
				System.out.println(getal + " is een priemgetal");
			}
			else{
				System.out.println(getal + " is geen priemgetal");
			}
			
		}
		catch (Exception e){
			System.out.println("Fout bij lezen." + e);
		}
	}
}

zal wel simpele manier zijn, maar het werkt :p
V

Vich

Legacy Member
killgore zei:
[...]

Dat is niet waar. Er zijn geoptimaliseerde technieken (zeefmethode of zo) die het berekenen wat sneller laten gaan.
Er is echter (nog) geen formule om bv. gegeven priemgetal n, priemgetal n+1 te verkrijgen.
Klik om te vergroten...

Ik zeg toch niet dat er geen geoptimaliseerde technieken zijn? ;) Juist daarom dat ik het noteerde als "semi-bruteforce".
Mijn punt is juist dat er zo geen formule is, dat was ook de bedoeling van m'n post.
I

Ice

Legacy Member
"if(x < 2 && x > 0){"

wat is er mis met if (x == 1) { ? Te duidelijk ofzo? Of ken jij nog gehele getallen die in ]0,2[ liggen?
M

M1tch

Legacy Member
tot de vierkantswortel? niet tot en met de helft van het getal?
[

[BAT] Hydra

Legacy Member
M1tch zei:
tot de vierkantswortel? niet tot en met de helft van het getal?
Klik om te vergroten...

Uiteraard enkel tot de vierkantswortel. Die is eigenlijk "de helft" van het getal door een delingsbril bekeken :).
k

killgore

Legacy Member
Vich zei:
Ik zeg toch niet dat er geen geoptimaliseerde technieken zijn? ;) Juist daarom dat ik het noteerde als "semi-bruteforce".
Mijn punt is juist dat er zo geen formule is, dat was ook de bedoeling van m'n post.
Klik om te vergroten...

k, misverstaan dan :).

en ivm maar tot wortel: is logisch he, stel dat er een getal y hoger dan sqrt(x) is waarvoor er een gehele oplossing z is:

x/y=z of x=z*y of x/z=y , en hier weet je dat z < sqrt(x) (anders kan z*y nooit x zijn).

Dus het is vrij nutteloos om hoger te gaan als sqrt.

In het programmeren komt het erop neer dat je stopt wanneer je deler (y) groter wordt dan je quotiënt (z).
T

TiZon

Legacy Member
Ik heb er dit van gemaakt:

Code: 
	public boolean isPriem(int g)
	{
		int deeltal=1;
		int delers=0;
		boolean priemgetal=false;
	
	while(deeltal<=g)
	{
		if(g%deeltal =0)
			delers++;
    
    deeltal++;
    }
    
    if(delers > 2)
    	priemgetal = false;
    else
    	priemgetal = true;
    	
    System.out.println(priemgetal);
    return priemgetal;
	}
M

MilM

Legacy Member
Zoals hierboven gezegd, enkel tot de vierkantswortel.
Anders tel je dubbel

3*6 en 6*3 komen namelijk hetzelfde getal uit

Dus zet uw deeltal op 2 en delers ook op 2 en dan dus vanaf 2 tot vierkantswortel beginne rekenen.
Geen reden om delen door 1 ook nog eens telkens te testen.

EDIT: g%deeltal =0 moet toch == zijn ?
D

Duffman-

Legacy Member
TiZon zei:
inderdaad, ik ga het even aanpassen ;)
Klik om te vergroten...

Hey,

volg jij T.I. @ KDG? Wij hebben namelijk net dit programmaatje moeten maken en aangezien jij je oplossing in C geef doe je mij vermoeden dat je -net als ik- een student Toegepaste Informatica bent. :p

Grtz,
Duffman-
T

Tyfius

Legacy Member
Duffman- zei:
Hey,

volg jij T.I. @ KDG? Wij hebben namelijk net dit programmaatje moeten maken en aangezien jij je oplossing in C geef doe je mij vermoeden dat je -net als ik- een student Toegepaste Informatica bent. :p

Grtz,
Duffman-
Klik om te vergroten...
"System.out.println()" en "public boolean" zijn geen C.
S

SMa

Legacy Member
ik herken die opdracht... ik heb het ook moeten maken in het eerste jaar

KaHo Sint-Lieven Gent?
ik vind het trouwens best wel erg dat je al zo vroeg in het jaar je werken laat maken op een forum, terwijl de docenten nochtans met veel plezier uitleg geven
het is altijd beter om zelf te zoeken, al ben je er uren aan bezig ;) leer je het meest van bij!
k

killgore

Legacy Member
TiZon zei:
Ik heb er dit van gemaakt:

Code: 
	public boolean isPriem(int g)
	{
		int deeltal=1;
		int delers=0;
		boolean priemgetal=false;
	
	while(deeltal<=g)
	{
		if(g%deeltal =0)
			delers++;
    
    deeltal++;
    }
    
    if(delers > 2)
    	priemgetal = false;
    else
    	priemgetal = true;
    	
    System.out.println(priemgetal);
    return priemgetal;
	}
Klik om te vergroten...

Code: 
	public static boolean isPriem(int g) {
		if(g<2) return false;
		int deler = 2;
		while (deler <= (g / deler)  ) {
			if ((g % (deler++)) == 0)
				return false;
		}
		return true;
	}

lijkt mij iets korter & simpeler nee?


Leer van in tijds-kritieke toepassingen nutteloze berekeningen te vermijden. Zodra je een deling hebt gevonden die rest 0 geeft is het geen priem meer en kan je false teruggeven, het controleren van al die andere getallen is compleet nutteloos.
Zelfde hier wrom ik die sqrt-benadering (vervangen door een computationeel vriendelijkere <= en /) gebruik, veel minder getallen af te lopen.
T

TiZon

Legacy Member
Hogent ;)
1 TIN idd, zal een vrij standaard-oefening zijn zeker ;)

Allemaal bedankt!
Het archief is een bevroren moment uit een vorige versie van dit forum, met andere regels en andere bazen. Deze posts weerspiegelen op geen enkele manier onze huidige ideeën, waarden of wereldbeelden en zijn op sommige plaatsen gecensureerd wegens ontoelaatbaar. Veel zijn in een andere tijdsgeest gemaakt, al dan niet ironisch - zoals in het ironische subforum Off-Topic - en zouden op dit moment niet meer gepost (mogen) worden. Toch bieden we dit archief nog graag aan als informatiedatabank en naslagwerk. Lees er hier meer over of start een gesprek met anderen.
Terug
Bovenaan