Java – find a simpler way to prime than this?
Is there a more effective, cleaner / more elegant way to find primes? The code works normally, but I just wrote some of the most logical things for me. I can't figure out any other way, but to be honest, it doesn't look good: P. I know coding is not the most elegant activity
This is my main method:
import java.util.Scanner;
public class DisplayPrimeNumbers
{
public static void main(String[] args)
{
Scanner scan = new Scanner(system.in);
System.out.print("Enter an integer that you'd like the system to print the prime numbers till: ");
String input1 = scan.nextLine();
int input = Integer.parseInt(input1);
PrimeGenerator prime = new PrimeGenerator(input);
for (int i = 1; i < input ; i++)
{
if(prime.isPrime())
{
System.out.println(prime.getNextPrime());
}
}
System.out.println(1);
}
}
This is my class:
public class PrimeGenerator
{
private int number;
public PrimeGenerator(int n)
{
number = n;
}
public int getNextPrime ()
{
return number+1;
}
public boolean isPrime()
{
for(int i = 2; i < number; i++)
{
if (number % i == 0)
{
number--;
return false;
}
}
number--;
return true;
}
}
Solution
Although this question has been answered, I think I will provide my answer anyway. I hope someone may find it very useful:
You seem to focus on elegance and efficiency I would also like to point out that correctness is equally important Unless you have special requirements to treat No. 1 as a prime, you don't think so anymore You should also consider the case when users enter primes You should also consider the boundary conditions of the numbers you print Especially if I enter the number 7, does your user want it to output 5,3,2,1 or 7,5,1 Although my personal preference is for the latter, using concise messages can make either option effective
grace
The main reason for the lack of elegance in your solution is that you combine two concepts: prime test and prime generation
The prime test is a (fast) method for determining whether a single arbitrarily selected number is prime Prime generator is a method of generating usually continuous prime sequences
As your program demonstrates, you can generate a continuous sequence of prime numbers by testing each number in a given range and selecting only those prime numbers! Taking this as our current basic strategy, let's figure out what the code may be:
According to our previous description, we say that prime test is a method (i.e. function) to determine whether some arbitrarily selected numbers are prime Therefore, this method should be used as the number of input a (n arbitrary selection) and return or no given quantity is prime (i.e. true / false) Let's see what it looks like:
public interface PrimeNumberTest
{
bool isPrime(int value);
}
And combine your prime test
public class BruteForcePrimeNumberTester : PrimeNumberTest
{
public bool isPrime(int value)
{
bool isPrime = true;
for(int i = 2; isPrime && i < value; i++)
{
if (value % i == 0)
{
isPrime = false;
}
}
return isPrime;
}
}
Then, your main program is responsible for iterating over each number and printing only the prime numbers. Test the thsoe that is identified as prime
public static void main(String[] args)
{
//Determine the range of prime numbers to print
Scanner scan = new Scanner(system.in);
System.out.print("Primes smaller than what number should be printed?: ");
int max = Integer.parseInt(scan.nextLine());
//Identify how prime numbers will be tested
PrimeNumberTest test = new BruteForcePrimeNumbertest();
//Uncomment the line below if you want to include the number 1. Favour adding it here so that you may
//use re-use your prime number test elsewhere that atually needs to kNow if a number is prime.
//System.out.println(1);
//Print the prime numbers
for (int i = 2; i < max ; i++)
{
if(test.isPrime(i))
{
System.out.println(i);
}
}
}
However, your main program should only focus on prime generation It doesn't really care how to generate the semantics of these primes. We just want primes It is not important to find prime numbers through prime tests or any other algorithm So let's ask ourselves what a prime generator is like?
For starters, prime numbers are always integers, so we should not store them in floating point numbers, doubles, or decimals Leave 32 - bit and 64 - bit integers If you want to generate larger primes, obviously you should use long, but I just want to use int. in other languages, we must also consider things like unsigned numbers
Now we need to find a way to return all these numbers at the same time Since we are going to generate a continuous sequence, trees really don't make sense The stack is meaningless because consumers usually want the numbers in the order they are generated Queues can be used because they comply with the first in first out rule In fact, this type is ideal if the end application has an asynchronous prime generator (producer) and a separate asynchronous consumer For this example, I want something read - only In essence, the prime generator is Iterable < int >
public class PrimeNumberTestGenerator : Iterable<int>
{
private int limit;
private PrimalityTester tester;
public PrimeNumberTestGenerator(PrimalityTester tester,int limit)
{
this.tester = tester;
this.limit = limit;
}
private class PrimeNumberIterator : Iterator<int>
{
private int current;
public PrimeNumberIterator()
{
}
public bool hasNext()
{
return next < limit;
}
public int moveNext()
{
if (!hasNext())
{
throw new NoSuchElementException();
}
int result = next;
do
{
next++;
} while(hasNext() && !tester.isPrime(next));
return result;
}
public void remove()
{
throw new UnsupportedOperationExecution();
}
}
public Iterator<int> iterator()
{
return new PrimeNumberIterator();
}
}
So how do we connect them?
public static void main(String[] args)
{
//Determine the range of prime numbers to print
Scanner scan = new Scanner(system.in);
System.out.print("Primes smaller than what number should be printed?: ");
int max = Integer.parseInt(scan.nextLine());
//Identify how prime numbers will be tested
Iterable<int> primes = new PrimeNumberTestGenerator(max,new BruteForcePrimeNumbertest());
//Print the prime numbers
foreach (int prime : primes)
{
System.out.println(prime);
}
}
efficiency
Now the other side of the problem is an effective method to determine prime numbers in a specified range Although fast Internet search should produce many different "fast" algorithms for determining a set of primes that are more secure than brute force methods One method is Atkin screening:
public class AtkinSieve : Iterable<int>
{
private BitSet primes;
public AtkinSieve(int limit)
{
primes = new BitSet(limit);
int root = (int)Math.sqrt(limit);
primes.set(2);
primes.set(3);
//this section can be further optimized but is the approach used by most samples
for (int x = 1; x <= root; x++)
{
for (int y = 1; y <= root; y++)
{
int number;
int remainder;
number = (4 * x * x) + (y * y);
remainder = number % 12;
if (number < limit && (remainder == 1 || remainder == 5))
{
primes.flip(number);
}
number = (3 * x * x) + (y * y);
remainder = number % 12;
if (number < limit && remainder == 7)
{
primes.flip(number);
}
if (x < y)
{
number = (3 * x * x) - (y * y);
remainder = number % 12;
if (number < limit && remainder == 11)
{
primes.flip(number);
}
}
}
}
for (int i = 5; i <= root; i++)
{
if (primes.get(i))
{
int square = i * i;
for (int j = square; j < limit; j += square)
{
primes.clear(j);
}
}
}
}
}
public class SetBitIterator : Iterator<int>
{
private BitSet bits;
private int next;
private bool isReadOnly;
public SetBitIterator(BitSet bits)
{
this.bits = bits;
next = bits.nextSetBit(0);
}
public bool hasNext()
{
return next <> -1;
}
public int moveNext()
{
int result = next;
next = bits.nextSetBit(next);
return result;
}
public void remove()
{
throw new UnsupportedOperationException();
}
}
Conveniently, we only need to change one line in the previous main program to use this prime generator!
Change:
//Identify how prime numbers will be tested Iterable<int> primes = new PrimeNumberTestGenerator(max,new BruteForcePrimeNumbertest());
To:
//Identify how prime numbers will be tested Iterable<int> primes = new AtkinSieve(max);