Program that verify that some numbers are prime?

Question

Ok so i made this program that verify if a number is prime.I can't figure out how to make a program that can verify that all numbers < n are prime.Can you help me ?

import javax.swing.*;

public class Main {

    public static void main(String[] args) {
        int i;
        int n;
        boolean nPrime=true;
        n = Integer.parseInt(JOptionPane.showInputDialog("Entrer un numero"));

        for (i = 2; i < n; i++) {
            if (n % i == 0) {
                nPrime = false;


            }
        }
        if (nPrime) {

            System.out.println("Le numero " + n + " est prime");
        } else
            System.out.println("Le numero " + n + " n'est pas prime");


    }
}

Do you want to print out all numbers which are prime between 2 and n? — rbr94, Oct 26 '16 at 20:03
Just add another if statement to check if it's less then n before setting the boolean value. — jthort, Oct 26 '16 at 20:03
Assuming one and zero are non-prime is there any n for which "all numbers < n are prime"? — Andreas, Oct 26 '16 at 20:04
@Andreas yes 3. Then it will be 3 and 2 and they are both prime. — rbr94, Oct 26 '16 at 20:05
Yea i want to introduce a number n say equal to 20 and to print all the prime numbers that are smaller than 20. — Bogdan Dragan, Oct 26 '16 at 20:07
oh, you're looking for https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes — Andreas, Oct 26 '16 at 20:08
@Andreas Yea i think that is.Is it bad i couldn't figure it out myself?...I am trying for 2 hours.I started college 1 month ago and is my first encounter with programming. — Bogdan Dragan, Oct 26 '16 at 20:17

Nikhil Pathania · Answer 1 · 2016-10-26T21:23:42.203

Well my answer has a better time-complexity if you have a lot of queries. We can pre-compute all prime numbers less than 1000005 in O(nlg(n)lg(n)) and then for each query it takes O(1) time to check whether number is prime or not. Algorithm used is Seive Of Eratosthenes

Here is a link if you want to know more about algorithm: http://www.geeksforgeeks.org/sieve-of-eratosthenes/

static int MAX = 1000005;
public static void preComputeSeive(){
    Arrays.fill(isPrime, true);

    isPrime[0] = isPrime[1] = false;

    for(int i = 2; i < MAX; i++){
        if(isPrime[i]){
            for(int j = i+i; j < MAX; j+=i){
               isPrime[j] = false; 
            }
        }
    }
}

static boolean isPrime[] = new boolean[MAX];
public static void main(String args[]) throws IOException
{
  int n = Integer.parseInt(JOptionPane.showInputDialog("Entrer un numero"));

  if(n >= MAX){
    System.out.println("Enter a valid number");
    return;
  }      

  preComputeSeive();
    // count primes
  for (int i = 2; i <= n; i++) {
  if (isPrime[i]) {
    System.out.println("Le numero " + i + " est prime");
  } else {
    System.out.println("Le numero " + i + " n'est pas prime");
  }
}

}

You may want to change the [magic number](http://stackoverflow.com/questions/47882/what-is-a-magic-number-and-why-is-it-bad) `1000000`; enter 1000002 I get a false positive and if I enter 100005 an exception is thrown. — Andreas, Oct 26 '16 at 21:11
@Andreas Exception is thrown at 100005 because i am checking for n strictly less than 1000005 — Nikhil Pathania, Oct 26 '16 at 21:25

mhasan · Answer 2 · 2016-10-26T20:30:34.213

1

With reduced number of loops

public static void main(String[] args) {
        int i;
        int n,m;
        m=(int)Math.sqrt(n);  
        boolean nPrime=true;
        n = Integer.parseInt(JOptionPane.showInputDialog("Entrer un numero"));

        for (i = 2; i <= m; i++) {
            if (n % i == 0) {
                nPrime = false;
                break;

            }
        }
        if (nPrime) {

            System.out.println("Le numero " + n + " est prime");
        } else
            System.out.println("Le numero " + n + " n'est pas prime");


    }

edited Oct 26 '16 at 20:30

answered Oct 26 '16 at 20:09

mhasan

3,703
1
18
37

You can limit `m` to `ceil(sqrt(n))`. – bradimus Oct 26 '16 at 20:14
(Not the downvoter) `n/2` is not necessarily wrong, but `sqrt(n) < n/2` for all `n > 4`. At `n=100`, you are looking at a max of `10` iterations vs `50`. At `n=10_000`, it's `100` vs `5000`. If you are trying to limit the number of iterations, you might as well do it as well as you can. – bradimus Oct 26 '16 at 20:23

score 1 · Answer 3 · answered Oct 26 '16 at 20:24

Do you mean find all the numbers smaller than n they are primary?

ArrayList<Integer> primes = new ArrayList();
int i;
int j;
boolean nPrime;

for (i = 2; i <= n; i++) {
    nPrime = true;
    for (j = 2; j <= (int) sqrt(i); j++) {
        if (i % j == 0) {
            nPrime = false;
            break;
        }
    if (nPrime) primes.add(i);
}

System.out.println("Primes: " + Arrays.toString(primes.toArray());

score 0 · Answer 4 · answered Oct 26 '16 at 20:13

stolen from http://introcs.cs.princeton.edu/java/14array/PrimeSieve.java.html

import javax.swing.*;


public class PrimeSieve {
  public static void main(String[] args) {
    int n = Integer.parseInt(JOptionPane.showInputDialog("Entrer un numero"));

    // initially assume all integers are prime
    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 factor = 2; factor * factor <= n; factor++) {

      // if factor is prime, then mark multiples of factor as nonprime
      // suffices to consider mutiples factor, factor+1, ...,  n/factor
      if (isPrime[factor]) {
        for (int j = factor; factor * j <= n; j++) {
          isPrime[factor * j] = false;
        }
      }
    }

    // count primes
    for (int i = 2; i <= n; i++) {
      if (isPrime[i]) {
        System.out.println("Le numero " + i + " est prime");
      } else {
        System.out.println("Le numero " + i + " n'est pas prime");
      }
    }
  }
}

Dont know why this is downvoted, seems legit. I am upvoting this — Nikhil Pathania, Oct 26 '16 at 20:21
this is one of the reasons i hate stack, even when you give correct answers people just downvote without even reading — Nikhil Pathania, Oct 26 '16 at 20:22
@NikhilPathania no biggie; happens all the time. Thanks for the upvote. — Andreas, Oct 26 '16 at 20:27

Gaurish Gangwar · Accepted Answer · 2016-10-26T20:37:13.580

I will try to answer your question by not changing your code very much.

import javax.swing.*;

public class Main {

    public static void main(String[] args) 
    {
        int i; 
        int n; //here is your number (say 20) and you need all primes below 20
        int number; // it will loop through all numbers between 2 to n
        boolean nPrime=true;
        n = Integer.parseInt(JOptionPane.showInputDialog("Entrer un numero"));

        for ( number = 2 ; number <= n ; ++number ) // for outer
        {
            for (i = 2; i < number; i++) //for inner
            /*from here it is simply your code which checks every number
            for primeness, BTW you need to check for only upto
            square_root(number) so change your code to i*i < number, I
            didn't changed it just to make it as similar to yours as
            possible
            */
            {
                if (number % i == 0) 
                {
                    nPrime = false;
                }
            }//for inner closed

            if (nPrime) 
            {
                System.out.println("Le numero " + number + " est prime");
            } 
            else
                System.out.println("Le numero " + number + " n'est pas prime");
                //if you need only primes then remove this else part
            nPrime=true;
        }//for outer closed
    }// main() closed
}//class closed

Program that verify that some numbers are prime?

5 Answers5