primtal

Du undersøger, om alle primtal op til kvadratroden af tallet, går op i tallet :-)
er det tilfældet, at en eller flere gør det, så er tallet ikke et primtal

Den superhurtige løsning: [ LINK ]

Man undersøger, om primtallene fra 2 op til √97627577 går op i 97627577.

Man tjekker hurtigt, om 3 går op i tallet ved at beregne tværsummen af tallet. Tallet er ulige, så 2 går ikke op i tallet. Tallet ender hverken på 0 eller 5, så det er heller ikke deleligt med 5.

#2

En anden superhurtig løsning er blot at taste tallet ind i google's søgefelt.

jeg skal jo formulere det på en måde så jeg kan vise at jeg har forstået det.  jeg tog kvadratroden af det og fik 9880,67 så skal jeg divider med alle primtal op til det ?

#5

Ja, det er korrekt.

Andre metoder

Brug af Fermats lille sætning  hvis p er et primtal og a er primisk med p er a^p-1 ≡ 1 mod p. Den metode er ikke sikker; men kan hurtigt afsløre de fleste ikke primtal

Rabin-Miller testen, der er en udvidelse af Fermats lille sætning er mere sikker.  Det er den man normalt bruger i forbindelse med RSA kryptering. Den er ikke 100% sikker. men hvis man tester med tilstrækkelig mange a'er er sandsynligheden for at det er en fejl, så lille, at man ser bort fra den
 

men skal komme tallet ikke væk da det er heltal vi har at gøre med? og hvornår stopper jeg med at dividere på tl 9880,67?

#8

Man stopper ved det største primtal mindre end √97627577 . Et primtal er et helt tal.

er der ikke en hurtig måde at gøre det på`? eller skal jeg til og dividere så lang for at for finde det sidste tal og så om det er et primtal eller ej?

Du skal stoppe når du ellers kommer op til det tal. 9880 er ikke et primtal, så den skal du ikke teste med 9879 ved jeg ikke om det er et primtal; men du bør teste det.

I praksis kender man ikke alle de store primtal, så man tester simpelthen alle ulige tal. Man kommer til at lave nogle overflødige tests, men det er hurtigere end at skulle finde alle primtal op til den grænse.

Med så stort et tal skal du kunne programmere for at du kan teste det. Ellers kan du bruge et CAS værktøj til det.

Vi har ikke lært så meget hvordan man bruger cas endnu, så jeg er lidt på skideren vis det ikke kan løses uden et program. og jeg ved ikke om det er lovligt at bruge en hjemmeside for at se om det er et primtal.

Hvis der ikke er nogle nemme tal, der går op kan du ikke klare det uden hjælp af programmer. Du kan prøve i et regneark at se om du kan finde et ulige tal der går op i tallet. Her må du så overveje hvor mange tal du vil teste. Hvis du ikke kan finde nogen, kan du kun besvare det ved brug af programmer

kender du et link så? fordi så har jeg tænkt mig at bruge det også forklare, hvad jeg ville gøre man kan ikke fordi det vil tage for lang tid og måske bliver udsikkert

#14

Du kan læse mere om, hvordan man faktoriserer hele tal her

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

#12

Hvis man ikke har lært at bruge et program skriver man sit eget, mega ikke optimerede program:

#include <iostream>
using namespace std;

int main()
{
    long long int tal;
    cout << "Indtast tal" << endl;
    cin >> tal;
    long long int a=2;
    while(a<tal)
    {
        //tjekker om nogle tal under tallet man vil tjekke er deleligt med tallet
        if(tal%a==0)
        {
        cout << tal << " er ikke et primtal" << endl;
        return 0;
        }
        a++;
    }
    //hvis ingen tal er delelige med tallet man vil tjekke er det et primtal
    cout << tal << " er et primtal" << endl;
    return 0;
}

#16

I din algoritme undersøges det, om tallene fra 2 op til (tal - 1) går op i det undersøgte tal, hvilket er meget ineffektivt, da det er tilstrækkeligt at stoppe ved (√(tal)) .

Dine kommentarlinjer

"//tjekker om nogle tal under tallet man vil tjekke er deleligt med tallet"     og

"//hvis ingen tal er delelige med tallet man vil tjekke er det et primtal"

er forkerte.

Det drejer sig i stedet om, hvorvidt tallet man vil tjekke er deleligt med de mindre tal. Du har byttet om på rollerne.

Effektivitet ?

Man laver en boolsk tabel på 9880 elementer, alle initieres = true.

Man tester så med tallet 2, og hvis denne division ikke går op, sættes alle lige boolske elementer = false.

Processoren prøver så med næste "true element", og hvis denne division (med 3) heller ikke går op, sættes hver tredie boolske element = false, osv.

Mekanismen er, at processoren, kun tester tal, der i den boolske tabel (stadig) = true. Processoren bruger tid på at finde det næste true-element i tabellen, og "stikker" coprocessoren denne divisor, mens coprocessoren dividerer løs.

Det er effektivitet, og for yderligere at sætte "speed på", kan man assemblerprogrammere det.

#18

Ja, det er jo fint, hvis man har både en processor og en coprocessor. Desuden bruges der en del tid på at sætte pariteten i hver n'te celle til false i hver loop, og her vil en del celler unødigt blive sat til false flere gange. Men det er klart mere effektivt end algoritmen i #16, hvis man husker at stoppe, hvis divisionen går op.

#19:  Jo, man skal nok huske at stoppe.     :)

Sådanne programmører har lært det, iflg. den "gamle redacteur", Lynch, ved "Ingeniøren". Her skulle de lave et program, der kunne finde elefanter i Afrika. Programmet startede så i Sydafrika, og søgte i striber nordpå. For nu det tilfælde, at programmet slet ikke kunne finde en elefant, og programmet derfor fortsatte nordpå op gennem Spanien, Frankrig, osv., havde programmørerne placeret en "dummyelefant" ved den nordlige kyst ud til Middelhavet, som programmet kunne finde, og dermed stoppe, inden det gik galt.

Har du en computer, der ikke har en coprocessor ? ?  Den er indbygget i processorchippen, anno 2014. Den kan både regne i heltal og floating point.

Processoren og coprocessoren udfører operationer i parallel. Man kan vel sige, at hvis processoren ikke kan følge med i disse "false-settings", er der ingen tid tabt, men at tidsbesparelsen bliver reduceret. I vore dages 64-bit processorer, kan processoren jo false-sette 8 bytes pr. instruktion. Man har Harvard-struktur, pipelines, DMA-kredse (Direct memory acces) og hele svineriet idag. Det er nærmest umuligt, i vore dage, at regne ud hvor ufatteligt kort tid det tager at false-sette 9880 elementer ved parallel-processing.

En boolsk variabels værdi gemmes ikke som en paritetsbit, der ikke er med i memory, men typisk som den mindst betydende bit i en byte, hvis disse boolske værdier ikke ligefrem er gemt som "bit-packed".