CODEWITHSUNDEEP
javaprimes
Ujjwal
Ujjwal

Reputation: 356

Count prime number till N

This code works fine to count prime number till n. The problem is when n value is large like 1000000 or more, then it takes long time to execute and print the output (more than 30 secs.). I want to fix this issue. Any help would be great. Below is the code: 

public class PrimeNotillN {

        public static void main(String[] args) {

            int n = 1000;
            int count = 0;

            for (int i = 2; i < n; i++) {
                boolean res = checkprime(i);
                if (res == true)
                    count++;
            }
            System.out.println("total prime number till " + n + " is " + count);
        }

        private static boolean checkprime(int n) {
            if (n == 1)
                return false;
            else {
                for (int i = 2; i <= n / 2; i++) {
                    if (n % i == 0) {

                        return false;
                    }
                }

                return true;
            }
        }
    }

Upvotes: 1

Views: 4864

Answers (5)

Girish Rathi
Girish Rathi

Reputation: 111

Sieve of Eratosthenes is a very famous and efficient algorithm to generate all small prime numbers up to around 1-10 million. This is an ancient algorithm given by a Greek mathematician named Eratosthenes. 

 public class CountPrimes {

  public static void main(String[] args) {
    System.out.println(countPrimes(1000000));
  }

  public static int countPrimes(int n) {
    boolean[] primes = new boolean[n +1];

    for(int i = 0 ; i <= n ; i++) {
        primes[i] = true;
    }

    primes[0] = false;
    primes[1] = false;

    for(int i = 2 ; i * i <= n ; i++) {
        if(primes[i]) {
            for(int j = i ; i * j <= n ; j++) {
                primes[j * i ] = false;
            }
        }   
    }

    int primeCounts = 0;
    for(int i = 2 ; i <= n ; i++) {
        if(primes[i]) {
            primeCounts++;
        }
    }

    return primeCounts;
  }

}

Upvotes: 2

Mad Scientist
Mad Scientist

Reputation: 340

Using the sieve of eratoshtenes approach and maintaining the cache of all prime numbers found 

    public int countPrimes(int n) {
    if(n==0){
        return 0;
    }else{
        boolean[] isPrime=new boolean[n];
        for(int i=2;i<n;i++){
            isPrime[i]=true;
        }

        for(int i=2;i*i<n;i++){
           if(!isPrime[i]){
               continue;
           }
            for(int j=i*i;j<n;j+=i){
                isPrime[j]=false;
            }
        }

        int counter=0;
        for(int i=2;i<n;i++){
            if(isPrime[i]){
                counter++;
            }
        }

        return counter;

    }
}

Upvotes: 0

GaidenFocus
GaidenFocus

Reputation: 373

Primes, other than 2, are never even. Primes are only divisible by 1 and iteslef.

Also you can check up to it's sqrt. If you find nothing by then then it's a prime.

        public bool IsPrime(double num)
    {
        bool isprime = true;
        double limit = Math.Sqrt(num);

        if (num % 2 == 0)
            return num == 2;

        if (num == 3 || num == 5 || num == 7)
            return true;

        for (int i = 3; i < limit; i++)
            if (num % 1 == 0)
                return false;

        return isprime;
    }

Upvotes: 1

Tagir Valeev
Tagir Valeev

Reputation: 100269

You can store found primes into list and make further checks only against them (Sieve of Eratosphenes):

import java.util.ArrayList;
import java.util.List;

public class PrimeNotillN {
    public static void main(String[] args) {
        int n = 1000000;
        int count = 0;
        List<Integer> primes = new ArrayList<>();

        for (int i = 2; i < n; i++) {
            boolean res = checkprime(primes, i);
            if (res) {
                count++;
                primes.add(i);
            }
        }
        System.out.println("total prime number till " + n + " is " + count);
    }

    private static boolean checkprime(List<Integer> primes, int n) {
        int fence = (int) Math.sqrt(n);
        for (int prime : primes) {
            if (n % prime == 0) {
                return false;
            }
            if (prime >= fence)
                break;
        }

        return true;
    }
}

Upvotes: 0

rgettman
rgettman

Reputation: 178293

The easiest change to make is to end the for loop in checkprime after i has reached the square root of n. The reason is that if you have found a factor greater than the square root of n, that implies that there was a factor less than the square root of n that should have been found already.

for (int i = 2; i <= Math.sqrt(n); i++) {

Additionally, if you need more speed, the best algorithm for printing all prime numbers up to a limit is the Sieve of Eratosthenes. That involves replacing what you have. You'll need an array in which you'll mark which numbers are composite. Starting with 2, you will mark all multiples of 2 as composite. Moving through the array, if you find a number that isn't marked composite, it's prime and you can print it. With each prime you encounter, you will mark all of that prime's multiples as composite as well.

Upvotes: 2

Related Questions