Loops and Prime Numbers

Question

Write a program that prompts the user for an integer and then prints out all prime numbers up to that integer. For example, when the user enters 20, the program should print 2 3 5 7 11 13 17 19 Recall that a number is a prime number if it is not divisible by any number except 1 and itself.

I am trying to write this program but I am having difficulties, can anyone show me how to write this code? This is what I have written but it is completely wrong.

import java.util.Scanner;

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

        System.out.print("Enter Integers: ");
        int x;
        int n = in.nextInt();

        for (int i = 2; i < n ; i++)
        {
            x = i;

            if (n % i != 0 && i % x != 0)
            {
                System.out.println(i);
            }
            x--;
        }
    }
}

What have you tried? What is it printing out right now? Do you have some pseudo code written down? There are gaps in the logic you're trying to implement. We can talk through this if you'd like. — CookieOfFortune, Sep 12 '13 at 17:45
Maybe try stepping through the program in a debugger and see what's going on? — Alex, Sep 12 '13 at 17:47
Read this: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes . It'll help you understand what you're doing wrong. :) — corgichu, Sep 12 '13 at 17:47
Google is your friend... https://www.google.com/search?q=finding+prime+numbers+in+java — blgt, Sep 12 '13 at 17:48
possible duplicate of [Most elegant way to generate prime numbers](http://stackoverflow.com/questions/1042902/most-elegant-way-to-generate-prime-numbers) — Kevin Ji, Sep 12 '13 at 17:49
@blgt Googling for pre-written examples isn't going to help OP understand why their code doesn't work. — Alex, Sep 12 '13 at 17:49
@Alex Neither will asking for help without having done any research — blgt, Sep 12 '13 at 17:53

score 1 · Accepted Answer · answered Sep 12 '13 at 18:59

Computes the number of primes less than or equal to N using the Sieve of Eratosthenes.

% java PrimeSieve 25 The number of primes <= 25 is 9

% java PrimeSieve 100 The number of primes <= 100 is 25

% java -Xmx100m PrimeSieve 100000000 The number of primes <= 100000000 is 5761455

% java PrimeSieve -Xmx1100m 1000000000 The number of primes <= 1000000000 is 50847534

The 110MB and 1100MB is the amount of memory you want to allocate to the program. If your computer has less, make this number smaller, but it may prevent you from solving the problem for very large values of N.

class PrimeSieve {
    public static void main(String[] args) { 
        int N = Integer.parseInt(args[0]);

        // 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 i = 2; i*i <= N; i++) {

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

        // count primes
        int primes = 0;
        for (int i = 2; i <= N; i++) {
            if (isPrime[i]){ primes++; System.out.print(i+", ");}
        }
        System.out.println("\nThe number of primes <= " + N + " is " + primes);
    }
}

score -1 · Answer 2 · answered Sep 12 '13 at 17:47

Use this method to check if a given int is a prime.

public static boolean isPrime(int a)
{
    if ( a == 2)
        return true;
    int midpoint = Math.round(a/2);
    for(int i = 2; i < midpoint; i++)
    {
        if(a % i == 0)
            return false;
    }
    return true;
}

Explanation: Loop through all the numbers until midpoint and modulus until you encounter 0 or not. If you encounter 0 then return false because we know that it is not prime, if we encounter no zero then we return true because it is prime.
We loop until midpoint because there is no need to loop further.

You can implement it in your loop via

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

There's little point giving someone a canned answer to homework. — Darius X., Sep 12 '13 at 17:49
I added explanation, also what if it is not homework? I loved prime numbers and did it for fun without homework, but I did ask for help before in Math exchange just like he did and was given an answer. And if it is homework, then shame on the asker and he will fail school anyway. — Quillion, Sep 12 '13 at 17:52

Loops and Prime Numbers

2 Answers2