Improving the speed of code

Question

0.00/5 (No votes)

See more:

My code successfully counts the number of primes before a given number, n. However, I need a way to improve the speed of it as it isn't efficient for extremely large numbers.

What I have tried:

public class Solution {
    public static int countPrimes(int n) {
        int count = 0;
        for(int i = 2; i < n; i++){
            if(IsPrime( i )){
                count++;
            }
        }
        return count;
    }
    public static boolean IsPrime(int num) {
        for(int i=2;i<=num/2;i++){
            if(num % i == 0){
                return false;
            }
        }
        return true
}

Posted 8-Aug-16 16:39pm

EpicKai

Updated 8-Aug-16 17:20pm

Add a Solution

Comments

CPallini 9-Aug-16 2:26am

There's no way to improve Java speed. Try using an actual programming language...
(just kidding)

3 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Patrice T · Answer 1 · 2016-08-08T16:54:00

Solution 1

Take advantage of common knowledge about prime numbers.
- After 2, all primes are odd, so no need to test even numbers.
- All compound numbers have a divisor below its square root.

Posted 8-Aug-16 16:54pm

Patrice T

Comments

CPallini 9-Aug-16 2:25am

5.

Patrice T 9-Aug-16 2:34am

Thank you

Andy Allinger · Answer 2 · 2016-08-08T17:04:00

If you can be satisfied with an approximate number of primes, look into some math theory, going back to Euler, who gave a function for the approximate number of primes less than a given number.

If you really need the exact count, there are better ways to find prime numbers. Look into the sieve methods and others, some of which are discussed here on code project.

Trivially, to improve the IsPrime function you have given here, the upper bound of the for loop should be i <= ceiling(sqrt(num)), because a non-prime number must have two factors, and one of them must be less than or equal to its square root. Also, the division by two should come before the loop, so then the loop may run:
for (i=3; i<=ceiling(sqrt(num)); i=i+2) { ...}
So then you only have to test odd divisors. Twice as fast.

Dave Kreskowiak · Answer 3 · 2016-08-08T17:20:00

There's more than one way to generate a list of primes. Methods that are FAR faster than the naive method you're using now. I encourage you to Google for prime number generators, like the Sieve of Eratosthenes. You don't have to generate a list of primes that stops exactly at the limit you want. You can generate a list larger than that and then only count up to the number you need.

Improving the speed of code

3 solutions

Solution 1

Solution 2

Solution 3

Add your solution here

Preview 0