Created
January 14, 2017 05:12
-
-
Save jonpchin/c749bbd9a4e910bfe59848aab8c3bc4d to your computer and use it in GitHub Desktop.
Prime Sieve
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <stdio.h> | |
| // this is the greatest possible prime number to store in sieve | |
| #define MAXPRIME 50000 | |
| int storage[MAXPRIME]; | |
| int main(){ | |
| int prime[MAXPRIME]; | |
| int i; | |
| // Initialize all prime numbers to true | |
| for(i=2; i<MAXPRIME; ++i){ | |
| prime[i]=1; | |
| } | |
| prime[0]=0; | |
| prime[1]=0; | |
| int j; | |
| int k; | |
| for (j=2; j*j<MAXPRIME; ++j){ | |
| // If prime[p] is not changed, then it is a prime | |
| if (prime[j] == 1){ | |
| // Update all multiples of p | |
| for (k=j*j; k<MAXPRIME; k += j){ | |
| prime[k] = 0; | |
| } | |
| } | |
| } | |
| // Store all prime numbers up to MAXPRIME in global storage array | |
| int start=0; | |
| for (i=2; i<=MAXPRIME; ++i){ | |
| if(prime[i] == 1){ | |
| storage[start] = i; | |
| ++start; | |
| } | |
| } | |
| for(i=0; i<792; i++){ | |
| printf("%d ", storage[i]); | |
| } | |
| return 0; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment