C - priemgetallen

Auteur: pj_muller00 - 09 november 2006 - 18:40 - Gekeurd door: Joel - Hits: 6271 - Aantal punten: 2.75 (2 stemmen)

Aangezien ik een andere methode heb om priemgetallen te berekenen zet ik ze maar even hier.

Deze is een pak sneller als die van Joël. (No offence hé

)

Ik zal even uitleggen hoe het werkt.
Er is een stelling die zegt dat je alle priemgetallen (behalve 2 en 3) kan schrijven als een veelvoud van 6 - of + 1.
!! Opgelet het zegt niet dat alle veelvouden van 6 + of - 1 priemgetallen zijn.

Hoe passen we dit concreet toe.
De eerste loop gaat telkens een nieuw mogelijk priemgetal aangeven (6n + - 1).
De tweede loop gaat dan delen door opnieuw de mogelijke priemgetallen.
Dit hoeft maar te gebeuren tot de vierkantwortel van het getal. Dit ga ik niet uitleggen, is zeer makkelijk te begrijpen

Ik ben er tamelijk ver mee gegaan, één volledige dag laten draaien en ik zat op het grootste priemgetal dat ze 20 jaar geleden hebben gevonden.

Als je dat van vandaag wilt breken, raad ik je toch aan naar een andere methode te zoeken.

Code:

php code - Bekijk de code zonder highlighting - Klap code in

#include <stdio.h>
#include <math.h>
void main(void){
   int n = 11;//declareren
   int t, sqrt_n;
   int while1 = 1;
   int while2 = 1;
   int i =1;
   int show = 10000;//Om de hoeveel priemgetallen moet hij laten zien. als je het leesbaar wilt houden zet je dit op een groot getal

   while(while1 == 1){//While true werkte niet :s vandaar :)
      t=6;
      sqrt_n = sqrt(n);

      while(while2 == 1){
        if(n%(t-1)==0){//deelt met 6n-1
            break;
        }
        if(n%(t+1)==0){//deelt met  6n+1
            break;
        }
        if (t>sqrt_n){//zodat het deelgetal niet te groot wordt
            i++;
            if((i%show)==0){
                i=1;
                printf("%d %s", n,"\n");
            }
            break;
        }
        t+=6;
      }
      if ((n+1)%6==0){// Ga van 6n-1 naar de 6n+1
          n+=2;
      }
      else{//Ga van de 6n+1 naar 6n-1
          n+=4;
      }// Deze if else is gedaan om een extra loop uit te sparen, en dus ook tijd
  }
}

#include <stdio.h>
#include <math.h>
void main(void){
   int n = 11;//declareren
   int t, sqrt_n;
   int while1 = 1;
   int while2 = 1;
   int i =1;
   int show = 10000;//Om de hoeveel priemgetallen moet hij laten zien. als je het leesbaar wilt houden zet je dit op een groot getal
 
   while(while1 == 1){//While true werkte niet :s vandaar :)
      t=6;
      sqrt_n = sqrt(n);
 
      while(while2 == 1){
        if(n%(t-1)==0){//deelt met 6n-1
            break;
        }
        if(n%(t+1)==0){//deelt met  6n+1
            break;
        }
        if (t>sqrt_n){//zodat het deelgetal niet te groot wordt
            i++;
            if((i%show)==0){
                i=1;
                printf("%d %s", n,"\n");
            }
            break;
        }
        t+=6;
      }
      if ((n+1)%6==0){// Ga van 6n-1 naar de 6n+1
          n+=2;
      }
      else{//Ga van de 6n+1 naar 6n-1
          n+=4;
      }// Deze if else is gedaan om een extra loop uit te sparen, en dus ook tijd
  }
}

Download code (.txt)

Stemmen

Niet ingelogd.

Reacties

Post een reactie

Lees de reacties (2)