/**
* A possible sequential algorithm for Sieve Of Eratosthenes.
*
*
* Minor changes for 2022
*
* @author Eric Jul
*
* @author Shiela Kristoffersen.
*
* Recreated from idea by:
* @author Magnus Espeland
*
* His code can be found here:
* https://github.uio.no/magnuesp/IN3030-v19/blob/master/magnuesp/Sieve/Sieve.java
*
* And recreated from implementation by:
* @author Kim Hilton
*
* His code can be found here:
* https://github.uio.no/kimsh/IN3030_V20/blob/master/Sample_Code/Oblig3/SequentialSieve.java
*
*
* Idea:
* In the spirit of writing cache friendly code, we want to decrease the size
* of our data set.
*
* Therefore, instead of representing the numbers by integers, we are
* representing each number as a bit in an array of bytes. Non-primes will have
* a bit value of 1, and primes will have the bit value 0.
*
* We also observe that all even numbers, except 2, are never primes (since
* they can be divided by 2), and so we only include the odd numbers in our
* data set.
*
* We have now in a single byte, managed to squeeze in a set of 16 numbers;
* each byte represents an odd number and in between are the even numbers.
*
* You can think of the first byte in the array (i.e. byte at index 0) like this:
*
* 16_____14_____12_____10_____8_____6_____4_____2_____ <-- Not represented
* | 15 | 13 | 11 | 9 | 7 | 5 | 3 | 1 | <-- The first byte
*
*
* Implementation:
* We map each number to a specific bit in the byte array, and mark them
* according to the rules of the sieve. Then we run through the byte array
* to collect all the unmarked numbers.
*
*
*/
class SieveOfEratosthenes {
/**
* Declaring all the global variables
*
*/
int n, root, numOfPrimes;
byte[] oddNumbers;
/**
* Constructor that initializes the global variables
* @param n Prime numbers up until (and including if prime) 'n' is found
*/
SieveOfEratosthenes(int n) {
this.n = n;
root = (int) Math.sqrt(n);
oddNumbers = new byte[(n / 16) + 1];
}
/**
* Performs the sieve and collects the primes produced by the sieve.
* @return An array containing all the primes up to and including 'n'.
*/
int[] getPrimes() {
if (n <= 1) return new int[0];
sieve();
return collectPrimes();
}
/**
* Iterates through the array to count the number of primes found,
* creates an array of that size and populates the new array with the primes.
* @return An array containing all the primes up to and including 'n'.
*/
private int[] collectPrimes() {
int start = (root % 2 == 0) ? root + 1 : root + 2;
for (int i = start; i <= n; i += 2)
if (isPrime(i))
numOfPrimes++;
int[] primes = new int[numOfPrimes];
primes[0] = 2;
int j = 1;
for (int i = 3; i <= n; i += 2)
if (isPrime(i))
primes[j++] = i;
return primes;
}
/**
* Performs the Sieve Of Eratosthenes
*/
private void sieve() {
mark(1);
numOfPrimes = 1;
int prime = nextPrime(1);
while (prime != -1) {
traverse(prime);
prime = nextPrime(prime);
numOfPrimes++;
}
}
/**
* Marks all odd number multiples of 'prime', starting from prime * prime.
* @param prime The prime used to mark the composite numbers.
*/
private void traverse(int prime) {
for (int i = prime*prime; i <= n; i += prime * 2)
mark(i);
}
/**
* Finds the next prime in the sequence. If there are no more left, it
* simply returns -1.
* @param prev The last prime that has been used to mark all non-primes.
* @return The next prime or -1 if there are no more primes.
*/
private int nextPrime(int prev) {
for (int i = prev + 2; i <= root; i += 2)
if (isPrime(i))
return i;
return -1;
}
/**
* Checks if a number is a prime number. If 'num' is prime, it returns true.
* If 'num' is composite, it returns false.
* @param num The number to check.
* @return A boolean; true if prime, false if not.
*/
private boolean isPrime(int num) {
int bitIndex = (num % 16) / 2;
int byteIndex = num / 16;
return (oddNumbers[byteIndex] & (1 << bitIndex)) == 0;
}
/**
* Marks the number 'num' as a composite number (non-prime)
* @param num The number to be marked non-prime.
*/
private void mark(int num) {
int bitIndex = (num % 16) / 2;
int byteIndex = num / 16;
oddNumbers[byteIndex] |= (1 << bitIndex);
}
/**
* Prints the primes found.
* @param primes The array containing all the primes.
*/
static void printPrimes(int[] primes) {
for (int prime : primes)
System.out.println(prime);
}
/**
* Expects a positive integer as an argument.
* @param args Contains the number up to which we want to find prime numbers.
*/
public static void main(String[] args) {
int n;
try {
n = Integer.parseInt(args[0]);
if (n <= 0) throw new Exception();
} catch(Exception e) {
System.out.println("Correct use of program is: " +
"java SieveOfEratosthenes where is a positive integer.");
return;
}
SieveOfEratosthenes soe = new SieveOfEratosthenes(n);
/**
* Getting all the primes equal to and below 'n'
*/
int[] primes = soe.getPrimes();
/**
* Printing the primes collected
*/
printPrimes(primes);
}
}