Finne primtall

[Erik Hosle]

Hei!

Noen som vet om en enkel metode å finne ut om et eller flere tall du har er et primtall?Hadde en eksamen oppg der du skulle forklare hvordan du fant ut at tallen du hadde var det. (Utelukker bruk av innlagte programmer på kalk )

[David Gabrielsen]

Tror det er ingen annen måte enn å øke nevneren med én for hver gang (start på 3 og til (( / 2) - 1), for deretter sjekke om det gir noe restverdi eller ikke.

 

Eksempel, tallet 17...

 

ingen vits i å sjekke om tallet er delelig med 2 fordi kun partall kan deles på 2, så vi starter på 3:

17 / 3 = 5,666666667

17 / 4 = 4,25

17 / 5 = 3,4

17 / 6 = 2,833333333

17 / 7 = 2,428571429

17 / 8 = 2,125

 

ingen vits i å sjekke på noe høyere nevner fordi dette vet vi vil gi rest, ergo : 17 er et primtall.

 

Blir litt kjedeligere med tallet 123512352345343 feks... :smirk:

 

Er tallet ditt et partall kan du jo utelukke om det er et primtall umiddelbart, men det viste du sikkert. ;-)

 

Mulig det finnes noen smartere måte, men jeg klarer ihvertfall ikke å se noen..

 

EDIT : Man trenger vel strengt tatt ikke sjekke på partall i nevner heller, for det vil jo alltid gi rest...

[Ole-Jørgen Søberg]

Tror følgende kan brukes:

Alle tall som ender på partall kan deles med 2, tall der tverrsummen er delelig på 3 kan deles med 3 og tall som ender på 0 eller 5 kan deles på 5 og disse er følgelig ikke primtall. Mener at alle andre tall er primtall, men har ikke sjekket så nøye.

F.eks. er tallet 23456789 et primtall da tverrsummen er 44 og det ender ikke på partall eller 5. Tallet 123456789 har tverrsummen 45 og er dermed IKKE primtall. Noen som vet andre regler?

 

Skjønte ikke denne regelen til David med partall i nevner der svaret alltid skal bli desimaltall. F.eks. 40/4=10 og her er 4 partall, men 10 er ikke desimaltall?

[David Gabrielsen]

...

Skjønte ikke denne regelen til David med partall i nevner der svaret alltid skal bli desimaltall. F.eks. 40/4=10 og her er 4 partall' date=' men 10 er ikke desimaltall? [/quote']

 

Har endret innlegget mitt nå. Jeg mente rest, ikke desimaltall :-)

[Ole-Jørgen Søberg]

EDIT : Man trenger vel strengt tatt ikke sjekke på partall i nevner heller' date=' for det vil jo alltid bli desimal... [/quote']

Det var denne jeg ikke forsto . Den første var vel grei?

[David Gabrielsen]

EDIT : Man trenger vel strengt tatt ikke sjekke på partall i nevner heller' date=' for det vil jo alltid bli desimal... [/quote']

Det var denne jeg ikke forsto . Den første var vel grei?

 

Da er den også endret til rest.. Var litt trøtt her.

 

For å spesifisere :

Altså, om man deler oddetallet X med et partall, så vil dette gi restverdi, derfor kun vits å øke nevneren med to for hver sjekk (om man starter på 3).

[Ole-Jørgen Søberg]

Takk for oppklaringen . Selvsagt får man desimaltall (eller helt tall + "rest") om man deler et oddetall med et partall. Oddetall kan kun deles med et annet tall om tverrsummen er delelig med 3 eller det ender på 5, men det har jeg nevnt før.

Så da ble vi så enige så . Bare jeg som ikke hadde lest hva du skrev over.

 

Edit: forøvrig er 123512352345343 et primtall (ikke ender det på et partall, heller ikke ender det på 0 eller 5 og tverrsummen er 46 som ikke kan deles på 3)

 

Egentlig er det nok å lære seg primtallene opp til 20. Sjelden man får bruk for noe mer (1,3,5,7,11,13,17 og 19)

[David Gabrielsen]

Bare så det er sagt : Ole-Jørgen sin måte er laaaangt mer elegant enn mitt forslag

[Ole-Jørgen Søberg]

Nå ja.... :grin: Bare hoster opp noe gammel lærdom etter hukommelsen... Tar alle mulige forbehold om riktigheten.

[David Gabrielsen]

På bakgrunn av Ole-Jørgen sin måte, lagde jeg et vb-script man kan bruke:

 

dim sjekktall
sjekktall = " "
do while(isnumeric(sjekktall) = false)
sjekktall = abs(inputbox("Skriv inn tallet du vil sjekke om er et primtall (Godtar kun tall)"))
loop

tverrsum = getTverrsum(sjekktall)
siste_tall = getLastDigit(sjekktall)
melding = "dette er ikke et primtall"

if(sjekktall = "3") then
melding = "dette er et primtall!"
end if

if siste_tall = 1 or siste_tall = 3 or siste_tall = 7 or siste_tall = 9 then
resttall = tverrsum MOD 3
if resttall <> 0 then
	melding = "dette er et primtall!"
end if
end if

msgbox melding

private function getTverrsum(my_number)
dim i, size, retval
size = len(my_number)
for i = 1 to size step 1
	retval = retval + clng(mid(my_number, i, 1))
next
getTverrsum = retval
end function

private function getLastDigit(my_number)
getLastDigit = mid(my_number, len(my_number))
end function

 

Lim inn innholdet i notepad, lagre fila som primtall.vbs (må ha vbs som extension), dobbeltklikk fila..

[Petter Aspelund]

Takk for oppklaringen . Selvsagt får man desimaltall (eller helt tall + "rest") om man deler et oddetall med et partall. Oddetall kan kun deles med et annet tall om tverrsummen er delelig med 3 eller det ender på 5' date=' men det har jeg nevnt før. [/quote']

 

Dette er nok desverre ikke riktig.

49 gir en tverrsum paa 13 (ikke delelig med 3), og ender ikke med 0 eller 5, saa da burde det etter din teori vaere et primtall. 49 er delelig med 7, og derfor ikke primtall.

77 gir en tversum paa 14, ender ikke med 0 eller 5, og er delelig med 7 og 11, og derfor heller ikke primtall.

91 gir en tverrsum paa 10, ender ikke med 0 eller 5, men er delelig med 7 og 13.

 

Edit:

Eneste maaten er nok aa proeve aa dele tallet du skal finne ut av med alle andre primtall som er intill kvadratroten av det tallet du jobber med (Det vil si at om du vil finne ut om 401 er et primtall, tar du kvadratroten av dette (20 komma ett eller annet), og sjekker om 401 er delelig med noen av primtallene mindre enn dette (2, 3, 5, 7, 11, 13, 17 og 19.)

 

Edit: foeroevring er ikke 123512352345343 et primtall, da det er delelig paa 13. (som gir 9500950180411)

[David Gabrielsen]

Takk for oppklaringen

 

Skal lage et nytt vanntett script :-)

[David Gabrielsen]

denne bør være vanntett... :-)

dim sjekktall
sjekktall = " "
do while(isnumeric(sjekktall) = false)
sjekktall = abs(inputbox("Skriv inn tallet du vil sjekke om er et primtall (Godtar kun tall)"))
loop

primtall = true
if sjekktall MOD 2 = 0 then
primtall = false
nevner = 2
else
maks_nevner = int(sjekktall / 2)
for nevner = 3 to maks_nevner step 2
	rest = sjekktall MOD nevner
	if rest = 0 then
		primtall = false
		exit for
	end if
next
end if	

if primtall = false then
msgbox sjekktall & " er ikke et primtall, og er delelig med " & nevner
else
msgbox sjekktall & " er et primtall!"
end if

[Ole-Jørgen Søberg]

Ooops. Bra vi fikk en oppklaring fra Petter. Min forklaring var nok ikke så "vanntett" som jeg først trodde (og håpet). Fint vi har gode "realister" her inne og gode programmerere som David . Imponerende script dette.

[lars strømsnes]

Egentlig er det nok å lære seg primtallene opp til 20. Sjelden man får bruk for noe mer (1,3,5,7,11,13,17 og 19)

 

Er ikke 2 også ett primtall?

 

2 er bare delelig på en, og seg selv...

[Ole-Jørgen Søberg]

javisst... :blush: selvsagt.

[David Gabrielsen]

javisst... :blush: selvsagt.

Men hvorfor telles ikke tallet 1 som et primtall?

 

Kilde : http://en.wikipedia.org/wiki/Prime_number

[Alexander Storvig]

Står i wikipedia:

 

In mathematics, a prime number (or a prime) is a natural number greater than 1