Skip to content

Instantly share code, notes, and snippets.

@pkshultz pkshultz/sieve.java
Created Mar 26, 2015

Embed
What would you like to do?
Sieve of Eratosthenes
// Sieve of Eratosthenes
public int sieve_of_eratosthenes(int input)
{
boolean [] is_prime = new boolean [input];
int number_of_primes = 0;
// Set all values to true
Arrays.fill(is_prime, Boolean.TRUE)
// Sift
for (int i = 2; i <= sqrt(input); i++)
{
if (is_prime[i])
{
for (int j = pow(i, 2); j < input; j++)
{
if ((j % i) == 0)
{
is_prime[j] = false;
}
}
}
}
// Collect number of primes
for (int i = 2; i < input; i++)
{
if (is_prime[i])
{
number_of_primes++;
System.out.println("%d %n", is_prime[i]);
}
}
return number_of_primes;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.