Member Avatar for konman795

I need to write a program to find the first 10 prime numbers, i.e. integers that are only evenly divisible by themselves and 1. The hint I got was to make a big array of booleans named "isprime" and mark off all the non-prime numbers as false, i.e. isprime[4] = false. Here's what I have but it's just printing all of the numbers anyway.

public class PrimeFinder 
{
    public static void main(String[] args) 
    {
        boolean[] isprime = new boolean[100];
        
        for(int i = 2; i < isprime.length; i++)
        {
            if(i-1 % i == 0)
            {
                isprime[i] = false;
            }
            isprime[i] = true;
        }
        
        for(int j = 0; j < isprime.length; j++)
        {
            if(isprime[j] == true){
            System.out.print(j);
            System.out.print(", ");
            }
        }
    }
}
  • 3 Contributors
  • 2 Replies
  • 787 Views
  • 10 Hours Discussion Span
  • Latest Post Latest Post by JamesCherrill

Dani AI

Generated

Two problems explain why the original program prints every number: the divisibility test mixes subtraction and modulus so it never identifies divisors (in Java % binds before -), and each loop iteration then overwrites any false mark by setting the slot back to true. 's suggestion to avoid resetting a value is on point, and is correct to recommend initializing the boolean array to true and only turning entries off for composites.

A safe, compact fix is the Sieve of Eratosthenes: initialize all entries true (except 0 and 1), iterate p from 2 up to sqrt(limit), and when p is still true mark every multiple of p (starting at p*p) as false. After the sieve finishes, walk the array and collect primes until ten are found. The code below implements that and stops after ten primes.

public class FirstTenPrimes {
    public static void main(String[] args) {
        int limit = 100;
        boolean[] isPrime = new boolean[limit];
        java.util.Arrays.fill(isPrime, true);
        if (limit > 0) isPrime[0] = false;
        if (limit > 1) isPrime[1] = false;

        for (int p = 2; p * p < limit; p++) {
            if (isPrime[p]) {
                for (int m = p * p; m < limit; m += p) isPrime[m] = false;
            }
        }

        int found = 0;
        StringBuilder out = new StringBuilder();
        for (int i = 2; i < limit && found < 10; i++) {
            if (isPrime[i]) {
                if (found > 0) out.append(", ");
                out.append(i);
                found++;
            }
        }
        System.out.println(out.toString());
    }
}

Notes: first ten primes end at 29, so a limit of 30 would suffice; 100 is a safe default. For very small counts a trial-division approach (check each candidate modulo divisors up to sqrt(candidate)) is simpler and fast enough. Common pitfalls to watch for: operator-precedence when combining % with other operators, and resetting flags after they have been marked non-prime.

Recommended Answers

All 2 Replies

Member Avatar for zeroliken 
if(i-1 % i == 0)
            {
                isprime[i] = false;
            }
            isprime[i] = true;

even if it ran through the if statement the value of isprime will still be changed to true, try using an else statement

Edited by zeroliken because: n/a
Member Avatar for JamesCherrill

The code that zeroliken quoted is your problem. Each time you loop with a new value of i you overwrite all the values from the previous pass of the loop.
The correct way to do the sieve algorithm is to start with the isPrime array set to all true, then in your loop change that to false for any number that you find to be not a prime. Never set any back to true again! When all the looping is finished any element of isPrime that is still true represents a prime number.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.