Do while løkke inde i en for løkke til løsning af primtal

et lille hint: du kan hoppe ud af en for loekke i utide ved at bruge break statement !

Din do-while køre uendeligt når det er et primtal.

andet lille hint: for at checke om n er et primtal behovber du kun dividere med tal op til kvadratrod(n)

Mange tak Arne, det gjorde lige programmet mindst 10 gange så hurtigt. Vil du have pointene? :)

endnu et par hint:

Du behøver slet ikke at tjekke for lige tal over 2.

og en raninement til arnes hint:

for at checke om n er et primtal behovber du kun dividere med *primtal*tal op til kvadratrod(n)

raninement -> rafinement

Grunden til jeg gør det på denne måde er at det skal udføres efter den matematiske model, Sieve of Eratosthenes. Men koden kunne måske stadig optimeres?

hvis tabel[j] ikke er sat er der ingen grund til at checke %j

og det kan optimere lidt da % er en forholdsvis dyr operation

Den algoritme du har der er nu altså ikke Sieve of Eratosthenes.

Ja, din kode kan optimeres med de hints du har fået. :^9

code snippet:

  for(i=2;i<=p;i++) sieve[i]=TRUE;
  for(i=2;i<=sqrtp;i++) if(sieve[i]) for(j=2*i;j<=p;j=j+i) sieve[j] = FALSE;

18/12-2007 19:58:11> der er jo sådan set netop det jeg siger sidst i 18/12-2007 19:47:53 :^)

jep

er jeg helt fuldstændigt forkert på den for at lave Sieve of Eratosthenes?

Ja, med den angivne algoritme er du. SoE bruger sådan set slet ikke % men ganger i stedet og fjerner multipla.

Som 18/12-2007 19:59:41

Nu er jeg ikke helt med, har du et forslag til hvordan dette gøres?

Arne har sådan set allerede givet koden.

Man starter med et aray op til den størelse man ønsker at finde primtallene inden for.

Trin 1) Så starter man med 2. Fra denne sætter man et hak henover alle multipla af 2: 4, 6, 8, 10, ... indtil man løber "ovenud" af arrayet.

Trin 2) Derefter går man vidre til det næste tal hvor der ikke allerede er et hak. Det er 3. Fra denne sætter man et hak henover alle multipla af 3: 6, 9, 12, 15, ... indtil man løber "ovenud" af arrayet.

Trin 3) Derefter går man vidre til det næste tal hvor der ikke allerede er et hak. Det er 5 (4 er der allered et hak i). Fra denne sætter man et hak henover alle multipla af 5: 10, 15, 20, 55, ... indtil man løber "ovenud" af arrayet.

... og sådan fortsætter man:

Trin 4) 6 er hallet af. 7 er det næste ...

Trin 5) 8 er hakket af, 9 er hakket af, 10 er hakket af, 11 er den næste ...

... og sådan fortsætter man ....

- til at man løber "ovenud" arrayet og ikke kan fortsætte mere.

sieve:

2 3 4 5 6 7 8 9 10

streg alle multipla af 2: 4, 6, 8, 10
streg alle multipla af 3: 6, 9

2, 3, 5 og 7 er tilbage

(det er ikke noedvendigt at strege multipla af 5 og 7 da de er stoerre end kvadratroden
af 10 og der er ingen grund til at strege multipla af noget der ikke er primtal)

ja okay, jeg havde håbet lidt på at selv lave en funktion, der gjorde det og ikke bruge sieve... men det er måske en meget stor mundfuld?

Algoritmen er drønsimpel, og den burde du kunne lave uden de større problemer.

Mit bedste eksempel er:
for(i=start;i<ulimit;i++){
            for(j=2;j<i;j++){
                u = i%j;
                if(u==0){
                    table[i] = 0;
                    break;                 
                }
            }
       
    }

Hvor start og ulimit er den nedre og øvre grænse for det interval, der skal søges efter primtal i. Men det er jo ikke den rigtigt algoritme. Jeg må indrømme, jeg ikke helt forstår hvad jeg skal lave om?

EoS starter altid fra 2 af. Du kan ikke starte andre steder, ellers giver den forkerte resultater.

Dernæst synes jeg at du skal glemme alt om den eksisterende kode, og kigge på beskivelserne i 18/12-2007 20:13:20 eller i 18/12-2007 20:14:33. Hvordan eftergøre du bedst dem med et array og to løkker.

Der skal slet ikke bruge % nogen steder, så hvs du får lyst til det, så er du på omveje. ;^)

Hehe ja okay, jeg er forholdsvis ny indenfor programmering, hvis du ikke har bemærket det ;) men jeg har brug for lidt hjælp til at komme igang med at lave min egen algoritme

Mit forslag er at du starter med at prøve den manuelt på et ternet ark papit. Hvert tern er et af tallene.

Tilsammen udgør alle tallene så et array.

Kom du videre med denne her?

Ikke ret meget, jeg kunne ikke lige komme frem til hvordan jeg får programmet til at udelukke alle multipla af 2 :/

Det gør du sådan (med en while-løkke):

    // Størrelsen på sien.
    const int maksTal = 100;

    // Initialisering af sien.
    char talFelt[maksTal+1];
    for (int tal = 2; tal <= maksTal; tal++)
        talFelt[tal] = ' ';

    // Fjern alle multpla af tallet 2.
    int tal = 2;  // Start med 2

    // Start ved første multipla af tallet.
    int afkrydsTal = tal + tal;

    // ... fortsæt med alle multipla indtil at vi løber ud over enden.
    while (afkrydsTal <= maksTal)
    {
        // Sæt kryds.
        talFelt[afkrydsTal] = 'X';

        // Tæl op til næste multipla,
        afkrydsTal += tal;
    }

    // Udskriv
    for (int tal = 2; tal <= maksTal; tal++)
    {
        if (talFelt[tal] == ' ')
            cout << tal << ' ';
    }
    cout << endl;

- eller sådan (med en for-løkke):

    // Størrelsen på sien.
    const int maksTal = 100;

    // Initialisering af sien.
    char talFelt[maksTal+1];
    for (int tal = 2; tal <= maksTal; tal++)
        talFelt[tal] = ' ';

    // Fjern alle multpla af tallet 2.
    int tal = 2;  // Start med 2

    // Start ved første multipla af tallet.
    for (int afkrydsTal = tal + tal; afkrydsTal <= maksTal; afkrydsTal += tal)
    {
        // Sæt kryds.
        talFelt[afkrydsTal] = 'X';
    }

    // Udskriv
    for (int tal = 2; tal <= maksTal; tal++)
    {
        if (talFelt[tal] == ' ')
            cout << tal << ' ';
    }
    cout << endl;

mange tak,, jeg skal så tage din kode og indsætte i en ny løkke?

Den del hvor at man starter med 2 tallet, skal ind i en løkke som går vidre til 3 bagefter og gør det samme.

Gider du lige forklare logikken i:
for (int afkrydsTal = tal + tal; afkrydsTal <= maksTal; afkrydsTal += tal)

:)

Ja da.

Vi skal ikke krydse af ud for tallet selv. Vi skal først starte fra det første multiplum:

afkrydsTal = tal+tal  (= 2*tal)

Vi skal fortsættt med at krydse af indtil at vi når ud over neden af der hvor sien går til:

afkrydsTal <= maksTal

Vi skal krydse af for hvert multiplum. Dvs når vi har krydet af ud for tallet afkrydsTal, så er det næste tal vi skal krydse af ved lig med afkrydsTal+tal.

afkrydsTal = afkrydsTal + tal

(hvilket kan skrives på den kortere form: "afkrydsTal += tal")

Håber at det var forståligt?

Har du helt opgivet denne her?

Hej nielle,

Jeg har overhovedet ikke opgivet det, jeg har bare haft meget arbejde her mellem jul og nytår, så har slet ikke fået set på det. Men det har jeg nu, og jeg forstår det må jeg sige, endelig :P

Du skal have mange tak for hjælpen :)
Gider du smide et svar?

Skal arne_v ikke også smide et svar (18/12-2007 19:47:12) ?

in case

Nu var I begge så behjælpelige så I får lov til at dele om pointene :) Men mange tak for hjælpen.