Last active
April 23, 2019 01:30
-
-
Save mkaz/7730fcaf5d140481da74fb009c524176 to your computer and use it in GitHub Desktop.
The Sieve of Eratosthenes - Find primes in Python, Golang, and C
This file contains 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
| #!/usr/bin/env python3 | |
| import os, string | |
| max = 1000000 | |
| # seed list with first two primes | |
| primes = [2,3] | |
| # set number | |
| start_num = 4 | |
| # range of numbers searching for primes | |
| for num in range(start_num, max): | |
| #intialize not-a-prime as false | |
| nap = 0 | |
| # cycle through list of known primes | |
| for prime in primes: | |
| # check if a previous prime divides evenly | |
| # into the current number -- if so the number | |
| # we are checking (num) is not a prime | |
| if (num % prime) == 0: | |
| nap = 1 | |
| break | |
| # if prime squared is bigger than the number | |
| # than we don't need to check any more | |
| if prime*prime > num: | |
| break | |
| # did we determine it's not a prime | |
| # if not, then we found a prime | |
| if nap != 1: | |
| # add prime to list of known primes | |
| primes.append(num) | |
| print(num) |
This file contains 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
| package main | |
| import "fmt" | |
| func main() { | |
| max := 1000000 | |
| primes := []int{2, 3} | |
| start_num := 4 | |
| // loop through numbers to max | |
| for num := start_num; num <= max; num++ { | |
| nap := false | |
| // check if a previous prime divides evenly | |
| // into the current number -- if so the number | |
| // we are checking (num) is not a prime | |
| for _, prime := range primes { | |
| if (num % prime) == 0 { | |
| nap = true | |
| break | |
| } | |
| // if prime squared is bigger than the number | |
| // than we don't need to check any more | |
| if prime*prime > num { | |
| break | |
| } | |
| } | |
| // did we determine it's not a prime | |
| // if not, then we found a prime | |
| if !nap { | |
| primes = append(primes, num) | |
| fmt.Println(num) | |
| } | |
| } | |
| } |
This file contains 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
| /* | |
| Prime Number Finder | |
| Marcus Kazmierczak, marcus@mkaz.com | |
| Created On: March 18, 2002 | |
| # findthem.c $Revision: 1.3 $ | |
| # Last Updated: $Date: 2002/03/19 06:59:11 $ | |
| */ | |
| #include <stdlib.h> | |
| #include <stdio.h> | |
| /*== start/stop range ==*/ | |
| #define START 5 // MUST BE ODD | |
| #define STOP 99999999 | |
| int main(void) | |
| { | |
| int nap; | |
| long num, c, i; | |
| long *prime; | |
| prime = malloc((STOP/3) * sizeof(long)); | |
| if (!prime) { printf("Memory Allocation Error."); exit(1); } | |
| prime[0] = 2; prime[1] = 3; | |
| c = 2; /*== initial primes ==*/ | |
| /*== only have to check odd numbers ==*/ | |
| for (num=START; num < STOP; num = num + 2) | |
| { | |
| nap = 0; // set not-a-prime false | |
| /*= cycle through list of known primes =*/ | |
| for (i=0; i < c; i++) | |
| { | |
| /*= check if a previous prime divides evenly =*/ | |
| /*= if so the number is not a prime =*/ | |
| if ((num % prime[i]) == 0) { nap = 1; break; } | |
| /*= stop if prime squared is bigger than the number =*/ | |
| if ((prime[i] * prime[i]) > num) { break; } | |
| } | |
| /*= if not-a-prime, then we found a prime =*/ | |
| if (nap != 1) | |
| { | |
| /*= add prime to list of known primes =*/ | |
| prime[c] = num; c++; | |
| printf("%d \n",num); | |
| } | |
| } | |
| free(prime); | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment