Skip to content

Instantly share code, notes, and snippets.

@mkaz

mkaz/prime-numbers-1.py

Last active Apr 23, 2019
Embed
What would you like to do?
The Sieve of Eratosthenes - Find primes in Python, Golang, and C
#!/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)
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)
}
}
}
/*
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