Hvordan finner jeg primtall
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
-
PeerGynt
- World works; done by its invalids
- Innlegg: 389
- Registrert: 25/09-2002 21:50
- Sted: Kristiansand
Heisann Olebrummm
Bakgrunn
Et primtall er et positivt heltall som er delelig kun med seg selv og 1. Et heltall n er delelig med et heltall d dersom n/d også er et positivt heltall. Tall som ikke er primtall kalles sammensatte tall, d.v.s de kan settes sammen av tallets faktorer (se faktorisering). tallet 1 er et spesialtilfelle som er hverken primtall eller sammensatt tall. Det minste primtallet er derfor 2. 2 er det eneste primtallet som er partall. Alle primtall bortsett ifra 2 kalles odde primtall.
Eksempler
9 er delelig med 9, 3 og 1. 9 er derfor et sammensatt tall, ikke et primtall
7 er kun delelig med 7 og 1 og er derfor et odde primtall
Primtall kan finnes ved å "sile" ut tall som ikke er primtall:
Skriv ned, i rekkefoelge, alle hetallene fra 2 til det hoeyetse tallet n som du oensker å finne. Stryk ut alle tall some er delelig med 2 (annenhvert tall). Velg det minste gjenvaerende tallet, som nå er 3, og stryk ut alle tallene som er delelig med dette (hvert tredje tall). Igjen, velg det minste gjenvaerende tallet. Dette er nå 5. Stryk ut alle tallene som er delelig med 5 (hvert femte tall). Fortsett slik helt til du har stroeket ut alle tallene delelig med int([rot][/rot]n). Alle tallene som står igjen er nå primtall.
Denne måten å finne primtall på kalles "Eratosthenes Sil".
Definisjon: int(x) er det stoerste heltallet mindre enn, eller lik x.
8)
Bakgrunn
Et primtall er et positivt heltall som er delelig kun med seg selv og 1. Et heltall n er delelig med et heltall d dersom n/d også er et positivt heltall. Tall som ikke er primtall kalles sammensatte tall, d.v.s de kan settes sammen av tallets faktorer (se faktorisering). tallet 1 er et spesialtilfelle som er hverken primtall eller sammensatt tall. Det minste primtallet er derfor 2. 2 er det eneste primtallet som er partall. Alle primtall bortsett ifra 2 kalles odde primtall.
Eksempler
9 er delelig med 9, 3 og 1. 9 er derfor et sammensatt tall, ikke et primtall
7 er kun delelig med 7 og 1 og er derfor et odde primtall
Primtall kan finnes ved å "sile" ut tall som ikke er primtall:
Skriv ned, i rekkefoelge, alle hetallene fra 2 til det hoeyetse tallet n som du oensker å finne. Stryk ut alle tall some er delelig med 2 (annenhvert tall). Velg det minste gjenvaerende tallet, som nå er 3, og stryk ut alle tallene som er delelig med dette (hvert tredje tall). Igjen, velg det minste gjenvaerende tallet. Dette er nå 5. Stryk ut alle tallene som er delelig med 5 (hvert femte tall). Fortsett slik helt til du har stroeket ut alle tallene delelig med int([rot][/rot]n). Alle tallene som står igjen er nå primtall.
Denne måten å finne primtall på kalles "Eratosthenes Sil".
Definisjon: int(x) er det stoerste heltallet mindre enn, eller lik x.
8)
-
PeerGynt
- World works; done by its invalids
- Innlegg: 389
- Registrert: 25/09-2002 21:50
- Sted: Kristiansand
Nå, - vell...
Det er nok en betydelig arbeidsmengde å gjoere dette for hånd, men siling er idell for programmering. Du kan forholdsvis enkelt lage et lite program på kalkulatoroen din som implementerer denne metoden.
Det finnes også funksjoner som spyr ut primtall, men disse er veldig ineffektive. Kanskje dette er bedre i ditt tilfelle, dersom primtallene du oensker å finne ikke er veldig store?
Det er nok en betydelig arbeidsmengde å gjoere dette for hånd, men siling er idell for programmering. Du kan forholdsvis enkelt lage et lite program på kalkulatoroen din som implementerer denne metoden.
Det finnes også funksjoner som spyr ut primtall, men disse er veldig ineffektive. Kanskje dette er bedre i ditt tilfelle, dersom primtallene du oensker å finne ikke er veldig store?