0
#include <stdio.h>
#include <math.h>

bool isPrime(long long int n) {
    if(n <= 1) {
        return false;
    } else {
        for(long long int i = 2; i <= sqrt(n); i++) {
            if(n % i == 0) {
                return false;
            }
        }
    }
    return true;
}

int main() {
    
    int cases;
    long long int num;
    scanf("%d", &cases);
    
    for(int i = 0; i < cases; i++) {
        scanf("%lld", &num);
        if(isPrime(num)) {
            printf("YES\n");
        } else {
            printf("NO\n");
        }
    }
    
    return 0;
}

Is there any way I could do to make this code run faster? I tried the Sieve of Eratosthenes algorithm but that was slower, and apparently this "try to divide a number from 2 to its square root" is faster, but not fast enough according to the online judge.

AB3
  • 67
  • 6
  • 1
    Define "faster". – Sourav Ghosh Sep 25 '20 at 12:34
  • 4
    You call the `sqrt()` function for every loop, you could just call it once, store the result in an integer and compare it with that integer. Do you enable compiler optimizations? – 12431234123412341234123 Sep 25 '20 at 12:38
  • 7
    You can make it twice as fast by starting at 3 and incrementing by two (you have to handle %2 outside the loop). –  Sep 25 '20 at 12:40
  • 2
    How big will `cases` and `num` be? When `num` is a prime number near `10**18`, the loop will run about `10**9` times and it will be too much for typical online judge system. My guess is you should use the Sieve of Eratosthenes algorithm because you have to process multiple queries. – MikeCAT Sep 25 '20 at 12:48
  • Why do you use `signed`? Would `unsigned` not be more suitable and maybe a tiny bit faster? – 12431234123412341234123 Sep 25 '20 at 12:48
  • 3
    The most basic improvement is indeed to only check odd numbers. You can check the thousands of other prime numbers posts present on SO for inspiration. – Lundin Sep 25 '20 at 12:50
  • 2
    If the input is small enough, you could embed all the primes below a threshold in a hardcoded array so you only have to test for them. So it is relevant how large the largest input will be. – 12431234123412341234123 Sep 25 '20 at 12:53
  • According to the online judge, the input (N) will be somewhere between [2 <= N <= 2^63-1]. – AB3 Sep 25 '20 at 12:54
  • Possible duplicate: https://stackoverflow.com/questions/4493645/fastest-primality-test – 12431234123412341234123 Sep 25 '20 at 13:06
  • 1
    Please give a look to more advanced algorithms like the [Miller-Rabin test](https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test) which should much faster for your problem. – Jérôme Richard Sep 25 '20 at 13:11
  • @JérômeRichard I tried that, while it is definitely faster, it's not as accurate as I'd hoped it to be. – AB3 Sep 25 '20 at 13:52
  • @baronoke Note that the test can be tuned to be deterministic (assuming the Riemann hypothesis is true) – Jérôme Richard Sep 25 '20 at 15:08
  • @baronoke You can use the Miller-Rabin test to exclude numbers that are not prime. The numbers you have left, which should be a small amount, can be checked with the algorithm you already use. – 12431234123412341234123 Sep 25 '20 at 16:45
  • Re: `I tried the Sieve of Eratosthenes` - did you build it once? Or for each case? – Vlad Feinstein Sep 25 '20 at 17:34
  • @VladFeinstein I built it once, right after int main() { – AB3 Sep 26 '20 at 01:44
  • Did you use its result in your `isPrime`? Can you show your code? That should be OK for the performance. – Vlad Feinstein Sep 26 '20 at 04:33
  • There will be about 139094145 prime numbers below `sqrt(2**63)==2**31.5`, you could store them. It is about 550 MB. For numbers smaller than `2**31.5` check if they are in the list for larger numbers check if it is dividable by any of them. But i do not know if the online judge will accept a program that needs > 500 MB of RAM. – 12431234123412341234123 Sep 28 '20 at 22:30

0 Answers0