how can i determine all prime numbers smaller than a given input value?

Question

Can anyone help me to determine all prime numbers smaller than a given input value using scanner with java8 .

Input: N integer> 0

Output: the table with prime numbers.

Example: for N = 10 the Output is : 2 3 5 7

this is my work so far:

class Main {
public static void main(String[] args) {
    int N;
    int[] result = null;

    try (Scanner scanner = new Scanner(new File(args[0]))) {
        N = Integer.parseInt(scanner.nextLine());
         
          for (int i = 0; i < (N/2)+1; i++) {
            if (N%i==0)
                result[i]=i;
        for (int j = 0; j < result.length; j++) {
            System.out.print(result[j]);
            if (j < result.length - 1) {
                System.out.print(" ");
            }
        }
        }
        System.out.println();
    }
    catch (FileNotFoundException ex) {
        throw new RuntimeException(ex);
    }
 }
}

You could use a [prime sieve](https://en.wikipedia.org/wiki/Generating_primes). — khelwood, Mar 26 '19 at 09:50
https://en.wikipedia.org/wiki/Primality_test, here you can choose you favorite method if you really want to make an algorithme. Bust honestly it think it would be easier for you to store an array with all primaries number under 10000 return a part of this array in you function. — Julien Maret, Mar 26 '19 at 09:51
@JulienMaret i need no much code the professor told me that is very simple :O — Mourad9, Mar 26 '19 at 10:07
@CarlosHeuberger i was just thinkig that prime number less than a given number can't be > (given number )/2 — Mourad9, Mar 26 '19 at 10:09
@Mourag9 It was a duplicate. You added the requirement for a scanner afterwards. — N8888, Mar 26 '19 at 10:10
Welcome to Stack Overflow. Does your code already work as desired? If not, what is the difference? What are you still missing? I am sorry, but as your question stands it is too unclear. — Ole V.V., Mar 26 '19 at 10:16
You do not provide a fundamental information: what is the largest N that you target ? Depending on this, the implementations can be quite different. — , Mar 26 '19 at 11:27
@OleV.V. you are correct, that was for divisor of a number, not prime less than a number. but my original comment / *question* is still valid why start with zero and why up to N/2 — user85421, Mar 26 '19 at 15:13

Akash Shah · Accepted Answer · 2019-03-26T12:10:13.610

your code problem is int i = 0 start with 0 and next line if (N%i==0) so 10/0 is not possible throw a error something like java.lang.ArithmeticException: / by zero is not possible

and you loop through result.length, you need to loop through i your parent loop and put condition inside if (N%i==0) and you need many changes saw my below answer and debug where you get unexpected output and follow.

brute Force

public static void main(String[] args) {
        int N = 50;
        List<Integer> result = new ArrayList<>();
        for (int i = 1; i < N; i++) {
            boolean isPrime = true;
            for (int j = 2; j < i - 1; j++) {
                if (i % j == 0) {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime) {
                result.add(i);
            }
        }
        result.forEach(System.out::println);

    }

optimize one using Math.sqrt reason

public static void main(String[] args) {
        int N = 101;
        List<Integer> result = new ArrayList<>();
        for (int i = 1; i <= N; i++) {
            boolean isPrime = true;
            for (int j = 2; j < Math.sqrt(i - 1); j++) {
                if (i % j == 0) {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime) {
                result.add(i);
            }
        }
        result.forEach(System.out::println);
}

using BigInteger.isProbablePrime see

public static void main(String[] args) {
        int N = 101;
        List<Integer> result = new ArrayList<>();

        for (long i = 1; i <= N; i++) {
            BigInteger integer = BigInteger.valueOf(i);
            if (integer.isProbablePrime(1)) {
                result.add((int) i);
            }
        }
        result.forEach(System.out::println);

    }

Updated 1:- that something you want

try (Scanner scanner = new Scanner(new File(args[0]))) {
            int N = Integer.parseInt(scanner.nextLine());
            int[] result = new int[N];
            int resultIncreamenter = 0;
            // here for loop logic can be replaced with above 3 logic
            for (int i = 1; i <= N; i++) {
                boolean isPrime = true;
                for (int j = 2; j < Math.sqrt(i - 1); j++) {
                    if (i % j == 0) {
                        isPrime = false;
                        break;
                    }
                }
                if (isPrime) {
                    result[resultIncreamenter++] = i;
                }
            }
            for (int j = 0; j < result.length; j++) {
                System.out.print(result[j]);
                if (j < result.length - 1) {
                    System.out.print(" ");
                }
            }
            System.out.println();
        } catch (FileNotFoundException ex) {
            throw new RuntimeException(ex);
        }

thanks :) but i always have a problem with the input with scanner ..! if you look for the 1st code i must change here /* for (int i = 0; i < (N/2)+1; i++) { if (N%i==0) result[i]=i; */ not in other places that what the professor say — Mourad9, Mar 26 '19 at 10:44
thanks would you give me you email plz i have something to ask for — Mourad9, Mar 26 '19 at 14:17

score 0 · Answer 2 · edited Mar 26 '19 at 15:21

The algorithm using the Sieve of Eratosthenes taken from here:

private static int findNumberOfPrimes(int length) {
    int numberOfPrimes = 1;
    if (length == 2) {
        return 1;
    }

    int[] arr = new int[length];
    //creating an array of numbers less than 'length'
    for (int i = 0; i < arr.length; i++) {
        arr[i] = i + 1;
    }
    //starting with first prime number 2, all the numbers divisible by 2(and upcoming) is replaced with -1
    for (int i = 2; i < arr.length && arr[i] != -1; i++) {

        for (int j = i; j < arr.length; j++) {
            if (arr[j] % arr[i] == 0) {
                arr[j] = -1;
                numberOfPrimes += 1;
            }
        }
    }
    return numberOfPrimes;
}

Update :

and this is how you list them :

package primelessthanN;

public class Main {

    public static void main(String[] args) {
        int j;
        int n;
        n = 10;

        for (j = 2; j <=n; j++) {
            if (isPrime(j))
                System.out.println(j);
        }
    }

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

here you count the number of primes not the primes themselves ! — Mourad9, Mar 26 '19 at 10:19
You didn't say you wanted the primes themselves. But I updated it to include that as well. You can make n equal to whatever. Here it is for the value of 10 — N8888, Mar 26 '19 at 10:28
i always have a problem with the input with scanner ..! if you look for the 1st code i must change here /* for (int i = 0; i < (N/2)+1; i++) { if (N%i==0) result[i]=i; */ not in other places that what the professor say — Mourad9, Mar 26 '19 at 10:33

Joop Eggen · Answer 3 · 2019-03-26T11:57:24.037

You lost the overview, though you have all functionality within reach.

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

public static void main(String[] args) {
    try (Scanner scanner = new Scanner(new File(args[0]))) {
        int N = Integer.parseInt(scanner.nextLine());

        boolean printed = false;
        for (int j = 2; j < N; j++) {
            if (isPrime(j)) {
                if (printed) {
                    System.out.print(" ");
                }
                System.out.print(j);
                printed = true;
            }
        }
        System.out.println();
    } catch (FileNotFoundException ex) {
        throw new RuntimeException(ex);
    }
}

Simply use abstractions like isPrime.

Now for improvements (your results array): use the already found primes instead of all numbers in testing:

public static boolean isPrime(int n, int[] priorPrimes, int primesCount) {
    for (int p : priorPrimes) {
        if (n%p == 0) {
            return false;
        }
    }
    return true;
}


public static void main(String[] args) {
    try (Scanner scanner = new Scanner(new File(args[0]))) {
        int N = Integer.parseInt(scanner.nextLine());

        int[] primes = new int[N];
        int primesCount = 0;
        boolean printed = false;
        for (int j = 2; j < N; j++) {
            if (isPrime(j)) {
                primes[primesCount] = j;
                ++primesCount;
                if (printed) {
                    System.out.print(" ");
                }
                System.out.print(j);
                printed = true;
            }
        }
        System.out.println();
    } catch (FileNotFoundException ex) {
        throw new RuntimeException(ex);
    }
}

how can i determine all prime numbers smaller than a given input value?

3 Answers3

Linked