{{ message }}

Instantly share code, notes, and snippets.

# mkaz/prime-numbers-1.py

Last active Apr 23, 2019
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 #include /*== 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 = 2; prime = 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); }