Ang. Primtal

Anta att man får en uppgift att kontrollera om talet N är ett primtal. Finns det en direkt formel för att kontrollera om talet N är ett primtal eller måste man ta någon typ av omväg?

Det finns väl ingen direkt formel så, men väl en hel del algoritmer. Den enklaste av dessa är väl att man testar att dela med alla positiva heltal upp till sqrt(N), och ser om det går. Många många fler finns beskrivna på

http://en.wikipedia.org/wiki/Primality_test

Som dbshw skrev så finns det ingen snabb magisk formel för tillfället. Men om man vill testa för hand på relativt små tal så kan man nöja sig med att kontrollera om N är delbart med något primtal mindre än eller lika med roten ur N. Detta eftersom alla icke-primtal kan faktoriseras i primtal och om en av primtalsfaktorerna är >sqrt(N) så är en annan <sqrt(N).

Sen finns det ju lite olika tumregler man kan ha när man kollar om ett tal är delbart med ett annat, exempelvis att om ett tal är delbart med 3 är summan av siffrorna i talet delbart med 3 exempelvis 111 som ger summan 1+1+1=3 delbart med 3 vilket även 111 är.

Varför är det så?

Jag visar för tresiffrigt tal, du kan generalisera det till flersiffriga. Antag att talet är abc, dvs 100a + 10b + c, då är siffersumman lika med a+b+c. Vi skriver 100a som 99a + a och 10b som 9b + b och c behåller vi. Då har vi

99a + a + 9b + b + c = (99a + 9b) + (a + b + c)

Delen 99a + 9b är alltid delbar med 3, och då återstår delen a+b+c.

Okej, problemet är att vi har en uppgift där vi ska visa att talet N aldrig kan vara ett primtal, där N följer en viss funktion(?). Jag vill inte visa uppgiften då jag fortfarande vill lösa den själv i så stor utsträckning som möjligt .

Utan att veta hur din uppgift ser ut så skulle jag misstänka att det man ska göra är att lyckas bryta ut en konstant, som ett exempel om N=2x^2-10x+28 så kan man bryta ut 2 från alla termer dvs N delbart med 2 för alla heltalsvärden på x => N kan inte vara ett primtal.

Skulle även kunna vara ett andragradspolynom som har två heltalsrötter så att det kan skrivas N = (n-a)(n-b), där alltså a och b är heltal. Då kan N bara vara ett primtal då n-a och n-b är enheter (dvs är +1 eller -1).