-
1.
#include <stdio.h>
-
2.
#include <math.h>
-
3.
#include <stdlib.h>
-
4.
const int max = 500000000; //checking all numbers between 2 and max*2 +1
-
5.
int main() {
-
6.
-
7.
char *numbers;
-
8.
numbers = (char *) malloc(sizeof(char)*max);
-
9.
-
10.
//int primes = 1; //2 is not in the inital list, so start off with 2 as a prime
-
11.
unsigned int currentNumber = 3;
-
12.
unsigned int arrayPosition = 0;
-
13.
unsigned int maxNum = (int) sqrtf((float)max*2)/2;
-
14.
unsigned int crossOff, x;
-
15.
-
16.
for(x = 0; x < max; x++) {
-
17.
numbers[x] = 1; //set everything to true
-
18.
}
-
19.
-
20.
while(arrayPosition <= maxNum){
-
21.
-
22.
if(numbers[arrayPosition]){
-
23.
crossOff = arrayPosition + currentNumber;
-
24.
//printf("crossing out multiples of %d\n", currentNumber);
-
25.
while(crossOff < max){
-
26.
numbers[crossOff] = 0;
-
27.
crossOff = crossOff + currentNumber;
-
28.
}
-
29.
//primes++;
-
30.
}
-
31.
arrayPosition++;
-
32.
currentNumber = arrayPosition*2 + 3;
-
33.
}
-
34.
-
35.
int primes = 1; //start counting with 2
-
36.
//printf("2 is a prime\n");
-
37.
for(arrayPosition = 0; arrayPosition < max; arrayPosition++){
-
38.
if(numbers[arrayPosition]){
-
39.
//currentNumber = arrayPosition*2 + 3;
-
40.
//printf("%d is a prime\n", currentNumber);
-
41.
primes++;
-
42.
}
-
43.
}
-
44.
-
45.
printf("Primes found: %d\n", primes);
-
46.
-
47.
return 0;
-
48.
}
by Guest
by Guest
by Guest
by Guest
by Guest