Count Prime Java Problem

Question

Given two positive integers A and B, assume A ≤ B. Write a program to count the number of
prime numbers in the range [A: B].

I tried 2 testCases which were 1 to 100 and 216291 to 586839. The first one gave me correct output which is 25, but the second one did not return any output. How to fix that?

Here is my code
https://code.sololearn.com/c8NT9elLWH2A/?ref=app

Answer 1

My guess is that you ran out of time in the second testcase. You need a much faster prime test.

The are some improvements that you can do already:
1) you do not need to go to the top limit. If a number n has a divisor, it always so happens that one of the factors is less or equal to the square root of n. Higher you don't need to search
2) you can use wheel factorization, the simplest being that all even numbers greater than 2 are not prime. There are larger wheels that can reduce the search space even further.
3) if numbers get too large, you may need to resort to probabilistic methods.

Answer 2

Could be a time out ...
There an efficient way to check if a number is prime or not .. lets say the number is N..

you dont need to chek between 1 to N..
instead you can check from 2 to Sqrt(N)

https://code.sololearn.com/ci6CIM7UHAeI/?ref=app

PS: https://stackoverflow.com/questions/5811151/why-do-we-check-up-to-the-square-root-of-a-number-to-determine-if-the-number-is

Answer 3

Thank you so much!!

Answer 4

You're welcome :)

Answer 5

I just found one error in the code (after fixed). When I type input which is 1 to 20, the correct output would be 8 but the program shows 9. How can I fix that?

Answer 6

Lily
since your previous code assumed 1 to be prime .. I did include it too .. but i dont think it should be there

You could use System.out.println(i); after line 30 in my code to see which numbers its evaluating as a valid prime ....

here's the code after correction (line 22) : https://code.sololearn.com/ckqjPr2xBJ4F/?ref=app

Answer 7

I got it. Thank you for your help.

Answer 8

Hallo