Prime Number Generator Logic

Question

I am supposed to make a class PrimeNumberGenerator which has a method nextPrime that will print out all prime numbers up to a number the user inputs.

Ex)

Enter a Number: 
20
2
3
5
7
11
13
17
19

Our teacher told us that we should use a nested for loop. I tried, but when I tried to make the inner (nested) loop, I got really confused.

Here is my code: (I'm going to make a tester class later)

public class PrimeGenerator {

    private int num;
    boolean isPrime;

    public PrimeGenerator(int n)
    {
        num = n;
    }

    public int nextPrime (int num)
    {
        for (int i=2; i < num; i++) // The first prime number is 2 and the prime numbers only have to go up to a number the user inputs. 
        {
            for (int j = 3; j<=i/2; j+=2) // The next prime number is 3 and I attempted to loop through to get the next odd number.
            {
                if (num % i == 0) //if the number (upper limit) mod a "prime number" is 0, then that means that number is not really "prime" after all. 
                {
                    break;
                }
            }
        }

        return num;
    }

}

Answer 1

I wrote this function which lists the first n prime numbers:

static void primes(int n) {
    int[] prime = new int[n];
    prime[0] = 2;
    int pp = 0;

    int i = 2;
    while(pp < n - 1) {
        int g = 1;
        for(int p = 0; p <= pp; p++) {
            if(i % prime[p] == 0) {
                g = prime[p];
                break;
            }
        }
        if(g == 1) {
            pp += 1;
            prime[pp] = i;
        }
        i += 1;
    }
    
    for(int z = 0; z < n; z++) {
        System.out.println(prime[z]);
    }
}

It also should be relatively fast because it checks the lowest amount of divsors necessary. (i think)

Answer 2

I use this way in generator, it works well.

const isPrime = (number) => {
  if (
    Number.isNaN(number) ||
    !Number.isFinite(number) ||
    number % 1 || //  check int number
    number < 2
  ) {
    return false;
  }
  let i = 2;
  const m = Math.ceil(Math.sqrt(number));
  let isPrime = true;
  while (i <= m) {
    if (number % i === 0) {
      isPrime = false;
      break;
    }
    i = i + 1;
  }
  return isPrime;
};

function* primeNumber() {
  let nextNumber = 2;
  while (true) {
    if (isPrime(nextNumber)) {
      yield nextNumber;
    }
    ++nextNumber;
  }
}

const iter = primeNumber();
for (const n of iter) {
  if (n > 100) iter.return("end");//end loop
  console.log(n);
}

You can call next to get prime number in order.

const iter = primeNumber();
console.log(iter.next())
console.log(iter.next())

include thoes function to your class.

Answer 3

Doing primality check on each and every number is inefficient in your case. Use Sieve_of_Eratosthenes instead, to find all prime numbers up to any given limit.

public class PrimeGenerator {

  private final BitSet primes;

  private int nextPrime = 0;

  /**
   * Sieve of Eratosthenes
   */
  public PrimeGenerator(final int LIMIT)
  {
    primes = new BitSet(LIMIT+1);
    primes.set(2, LIMIT);

    for (int i = 4; i < LIMIT; i += 2)
      primes.clear(i);

    final int SQRT = (int) Math.sqrt(LIMIT);
    for (int p = 3; p <= SQRT; p = primes.nextSetBit(p+2)) {
      for (int j = p * p; j <= LIMIT; j += 2 * p) {
        primes.clear(j);
      }
    }
  }

  public int nextPrime()
  {
    nextPrime = primes.nextSetBit(nextPrime + 1);
    return nextPrime;
  }

  public static void main(String[] args) {
    // print primes up to 1000
    PrimeGenerator primeGen = new PrimeGenerator(50);
    int prime = primeGen.nextPrime();
    while (prime != -1) {
      System.out.println(prime);
      prime = primeGen.nextPrime();
    }
  }
}

Optimization tips when implementing Sieve of Eratosthenes:

• Iterate only over the odd numbers. Because all the multiples of 2, except for 2 is composite.

• Start eliminating from (p * p). So for instance for the prime number 3, you should start eliminating from 9.

• Increment by 2 * p instead of p, so to avoid even numbers.

This could generate millions of primes in just seconds.

Answer 4

Here is my Soluction.

public class PrimeNumberGenerator {

public static void print(int n) {
    // since 1 is not prime number.
    for (int i = 2; i <= n; i++) {
        if (isPrime(i)) {
            System.out.print(i + "\n");
        }
    }

}

public static boolean isPrime(int num) {

    for (int i = 2; i * i <= num; i++) {
        if (num % i == 0) {
            return false;
        }
    }

    return true;
}

public static void main(String[] args) {
    print(10);
  }

}

Output: 2 3 5 7

Answer 5

I think there could be a faster solution for that....

We all know that 2 is the first prime number,and a prime number is one which is just divisible by 1 and itself.

Let N = number entered by user till where we have to print the prime. Now,

if(N<2)
// No prime numbers

if(N==2)
// Print 2

if(N>2)
//print 2
 Create a list(or any resize able data structure)   and add 2 to it.
 now,
 run a loop from i= 3 to i<=n
{
         count how many numbers in the list are able to divide i completely(Let c                   
denotes it)
  if(c==0)
//print the number as it is prime
 }

Answer 6

I know the question is for a while out here but since no one posted java8/stream approach solution, here is one of the possible ways.

Gist can be forked here.

Print output: [1, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]

import java.util.*;
import java.util.stream.Stream;

import static java.util.stream.Collectors.toList;


public class PrimeNumber {

     /**
     * Java 8 / Lambda approach to generate Prime number.
     * Prime always start to look from number 1.
     * @param series Number of how many Prime number should be generated
     * @return List holding resulting Prime number.
     */
    public static List<Integer> generate(int series) {
        Set<Integer> set = new TreeSet<>();
        return Stream.iterate(1, i -> ++i)
                .filter(i -> i %2 != 0)
                .filter(i -> {
                    set.add(i);
                    return 0 == set.stream()
                            .filter(p -> p != 1)
                            .filter(p -> !Objects.equals(p, i))
                            .filter(p -> i % p == 0)
                            .count();
                })
                .limit(series)
                .collect(toList());
    }

    // Let's test it!
    public static void main(String[] args) {
        List<Integer> generate = PrimeNumber.generate(20);
        System.out.println(generate);
    }
}

Answer 7

Check out my code:

import java.util.Scanner;

public class c4 {

        public static void main(String[] args) {
            Scanner sn = new Scanner(System.in);

            System.out.println("Enter number");

            int num = sn.nextInt();

            if (num==1){
                System.out.println("Nor Prime Neither Composite");
            }
            for (int i=2;i<num;i++){
                int n=num%i;

                if (n==0){
                    System.out.println("It is a composite number");
                    break;
                }
               else{
                   System.out.println("it is a prime number");
                   break;
               }
           }
       }
    }

Answer 8

There are two questions here that you have forgotten to ask:

• Why does the nested loop make everything so complicated?
• What can I do to uncomplicate things again?

So let's play along with the question you actually asked, and then answer the first two questions.

What you want to do can probably be described as such: For every number, 1-n, where n is input by the user, print it if it's prime.

Okay, so let's write up the pseudocode/logic here. It looks like Java, but it isn't. It's just meant to convey what we're going for:

int largestNumber = readIntegerFromKeyboard();

for all ints i from 1 to largestNumber {
    if(isPrime(i)) {
        println(i);
    }
}

So let's do this! But first, we need a laundry-list of all the things we need to do:

• read integer from keyboard
• loop over numbers
• check if the number is a prime
• print primes (with newlines)

Let's just do the two easy things first. Reading the input and setting up the loop:

Scanner keyboard = new Scanner(System.in);
int largestNumber = keyboard.nextInt();

for(int i = 1; i <= largestNumber; ++i) {
    if(isPrime(i)) {
        System.out.println(i);
    }
}    

keyboard.close();

Okay, that seems simple enough. So far, everything here makes sense. It's easy to understand the logic. Now however, when we replace isPrime with actual logic, everything is about to get cluttered and hard to read.

So let's write this code as easy to understand as possible. We will use no tricks to speed up the code. Readability and correctness are the only two things we will care about. We will use the modulo operator to check if something is evenly dividable. Modulo is like integer division, except that it returns the remainder and not the result. so 7 / 2 = 2. 7 % 2 = 1, because there's one left over.

Scanner keyboard = new Scanner(System.in);
int largestNumber = keyboard.nextInt();

for(int i = 1; i <= largestNumber; ++i) {
    // checks if the number is a prime or not
    boolean isPrime = true;
    for(int check = 2; check < i; ++check) {
        if(i % check == 0) {
            isPrime = false;
        }
    }
    if(isPrime) {
        System.out.println(i);
    }
}    

So the good news is, this works. The bad news is, this is harder to read than necessary. And it's not a lot we can do here. When I wrote this up, I made several stupid mistakes, mixing up the variables. Maybe I'm stupid. So maybe I should in that case write stupid-proof code. ;) You on the other hand is not stupid. But you may work with me, who is stupid, so you kind of have to write stupid-proof code yourself, so that you can productively work with me.

The big problem is that we have this massive loop in the middle of the other loop. This is what tripped me up. I referred to the wrong loop variable. But why do we need a loop in a loop? Wasn't it much more comfortable to read:

if(isPrime(i)) {
    System.out.println(i);
}

Instead of that whole mess? Your professor pointed out the nested loops. But it threw you off. Instead, just write the isPrime method. And the fact is, that this is true for every single instance of nested loops I have ever come across.. So let's see how that would look instead:

class Homework {
    public static void main(String[] args) {
        Scanner keyboard = new Scanner(System.in);
        int largestNumber = keyboard.nextInt();

        for(int i = 1; i <= largestNumber; ++i) {
            if(isPrime(i)) {
                System.out.println(i);
            }
        }
        keyboard.close();
    }

    /**
     * Checks is a positive integer is a prime number
     */
    public static boolean isPrime(int number) {
        for(int check = 2; check < number; ++check) {
            if(number % check == 0) {
                return false;
            }
        }
        return true;
    }
}

That to me is a whole lot easier to read. Not because the logic got easier, but because the only thing I had to care about was either:

• Checking all the numbers and printing the correct ones, or
• how to check that a number is a prime.

Since these two separate things are now apart, you have much less to think about at once. Rejoice, for you have just done a proper abstraction. This makes your code easier to understand, because it separates out the two concerns. This is a key way of making larger projects. You take difficult things and do them by themselves. Then you can test them by themselves, and use them by themselves.

(Now I only have to await the downvotes for answering a question you didn't explicitly ask...)

Answer 9

package test;

import java.util.Scanner;

public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner reader = new Scanner(System.in);  // Reading from System.in
        System.out.println("Please Enter number you wanted prime number to be generated");
        int n = reader.nextInt();
        reader.close();

        Prime t1 = new Prime();
        for (int i = 2; i <= n; i++) {
            t1.x(i);
        }
    }

    public void x(int n) {
        // TODO Auto-generated method stub
        // TODO Auto-generated constructor stub
        int k = n - 1;
        int f = 0;
        if (n == 2) {
            f = 1;
        }
        for (int i = 2; i <= k; i++) {
            if (n % i == 0)
                break;
            else if (k == i) {
                f = 1;
            }
        }
        if (f == 1) {
            System.out.println("is prime" + n);
        }

    }
}

Answer 10

import java.util.regex.Matcher;
import java.util.regex.Pattern;

import javax.xml.soap.Node;

public class mainone {

 public static void main(String args[]){

    int[] primenumber=new int[13];

    for(int a=2,j=0;a<=14;a++,j++){
        primenumber[j]=a;

    }

    for(int b=1;b<13;b++){
        int d=primenumber[b];
        if(d%2==0){
            primenumber[b]=0;
        }

        for(int c=2;c<13;c++){
            int e=primenumber[c];
            if(e>0){
                for(int f=c+1;f<13;f++){
                    int g=primenumber[f];
                    if((g>0)&(g%e==0)){
                        primenumber[f]=0;
                    }


                }
            }
        }
    }


    for(int j=0;j<13;j++){
        System.out.println(primenumber[j]);
    }
     }

 }

Answer 11

To generate prime number simply loop through a given number and check if that number is prime or not. For efficient prime number generation IsPrime method must be very efficient and fast. So here is code to check if given number is prime or not very efficiently.

public static boolean IsPrime(int n) {

    if (n > 2 && n %2 == 0){
        return false;
    }
    int top = (int)Math.sqrt(n)+1;
    for (int i=3;i<top;i+=2){
        if (n%i==0){
            return false;
        }
    }
    return true;
}

Here is the code that will generate prime number between 1 and given number.

 public class GeneratePrimeNumber {
    public static void main(String[] args) {
    System.out.println("Enter number to get prime number");
    int n = new Scanner(System.in).nextInt();
        for (int j=0;j<n;j++){
            if (IsPrime(j)){
                System.out.print(j + " ");
            }
        }

    }
 }

Answer 12

Check this algorithm based on the sieve of Eratosthenes for prime numbers. Of course you need to adapt it to your program.

boolean isPrime[] = new boolean [N+1];
for (int i=2; i <=N; i++)
    isPrime[i] = true;

//mark non-primes <=N using Sieve of Eratosthenes
for (int i=2; i*i<=N; i++) 
{
    //if is a prime,then mark multiples of i as non prime 
    for (int j=i; i*j<=N; j++) 
    {
        isPrime[i*j] = false;
    }
}

for (int i=2; i<=N; i++) 
    if (isPrime[i])
        //Do something.......   

Answer 13

public class PrimeNumberGeneration {

public static void main(String[] args) {
    // TODO Auto-generated method stub

    Scanner scan = new Scanner(System.in);
    int n = scan.nextInt();

    ArrayList<Integer> primeNumbers = new ArrayList<Integer>();
    primeNumbers.add(2);
    System.out.println(2);

    no_loop:
    for(int no=3; no<=n; no+=2){
        for(Integer primeNumber: primeNumbers){
            if((no%primeNumber)==0){
                continue no_loop;
            }
        }
        primeNumbers.add(no);
        System.out.println(no);
    }

}

}

Answer 14

Try this code to generate prime number series

public class prime1 {

public static void main(String[] args) {

    int max = 100;

    System.out.println("Generate Prime numbers between 1 and " + max);

    // loop through the numbers one by one
    for (int i = 1; i < max; i++) {

        boolean isPrimeNumber = true;

        // check to see if the number is prime
        for (int j = 2; j < i; j++) {
            if (i % j == 0) {
                isPrimeNumber = false;
                break; // exit the inner for loop
            }
        }

        // print the number if prime
        if (isPrimeNumber) {
            System.out.print(i + " ");
        }
    }

}

}

Answer 15

Simple definition of a prime number: A number that is only divisible by one and by itself. By definition 1 isn't prime. Here is a brute force algorithm to determine if a number is prime or not.

    boolean isPrime(int n)
    {
        for (int i = 2; i < n; i++)
            if (n % i == 0)
                return false;
        return true;
    }