Prime or not Prime output slow

Question

This is C program. This is my code in the below. I used nano in terminal. When I compile and test with ./a.out 9872349901 but it's took me exact one minute to get a result... Does anybody know why is it slow? (I believe it probably is too long number but I used int isprime(long long n) {This is for my CS course class when I do labcheck, it is automated assignment grade to get points but it won't show up mine because labcheck wouldn't wait for it.

/**
 * Make a function called isprime that returns true (i.e. 1) if the integer
 * number passed to it is prime and false (i.e. 0) if it is composite (i.e.
 * not prime.)  A number is composite if it is divisible by 2 or any odd number
 * up to the square root of the number itself, otherwise it is prime.
 * Hint: n is divisible by m if (n % m == 0)
 */

/**
 * Using the isprime function you made above, test if a number provided on the
 * command line is prime or not. The program should print a usage message if no
 * number is provided ("Usage: p4 <number>\n") and print a warning if the number
 * is less than 2 ("input number should be > 1\n") and should be able to handle
 * numbers greater than 4 billion.
 * 
 * Example input/output:
 * ./p4 9872349901
 * 9872349901 is prime
 * ./p4 65
 * 65 is not prime
 */

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>

int isprime(long long n) {
    for (long long i = 2; i != n; ++i)
        if (n%i == 0)
            return 0;
    return 1;
}

int main (int argc, char *argv[])
{
    if (argc < 2)
    {
        printf ("Usage: p4 <number>\n");
        return -1;
    }
    char* p;
    long long n = strtoll(argv[1], &p, 10);
    if (n < 2 || *p != '\0')
    {
        printf ("input wrong\n");
        return -1;
    }
    int result = isprime(n);

    if (result == 1)
        printf ("%lld is prime\n", n);
    else
        printf ("%lld is not prime\n", n);
    return 0;
}

Many different numbers works perfectly but not for 9872349901 because that's the number what the instructor would test my assignment.

Here is my preview when I do "lab check"

cs25681@cs:/instructor/class/cs25681/cs/h5> labcheck 5
Checking assignment #5:
p1:
p2:
p3:
p4:
-3.0 output of program (p4) is not correct for input '9872349901':
------ Yours: ------
---- Reference: ----
9872349901 is prime
--------------------
p5:
p6:
p7:
p8:

I wanted to test it for each different number so here is preview with ./a.out <number>

cs25681@cs:/lecture/class/cs25681/cs> ./a.out 3
3 is prime
cs25681@cs:/lecture/class/cs25681/cs> ./a.out 1
input wrong
cs25681@cs:/lecture/class/cs25681/cs> ./a.out 9
9 is not prime
cs25681@cs:/lecture/class/cs25681/cs> ./a.out 9872349901
9872349901 is prime
cs25681@cs:/lecture/class/cs25681/cs> echo "took 43 seconds to output"
took 43 seconds to output
cs25681@cs:/lecture/class/cs25681/cs> 

Answer 1

^{Transferring a comment of mine into an answer.}

Use:

for (long long i = 2; i * i <= n; ++i)

This limits the testing until i is just greater than the square root of n, as suggested in the notes in your code.

A better algorithm would test 2, then test odd numbers 3, 5, 7, …, which reduces the amount of testing by a lot.

Better still, test 2 and 3, then 6*N±1 for N = 1, 2, 3, … which tests 5, 7, 11, 13, 17, 19, 23, 25 (which is the first time it isn't picking a prime pair), etc.

if (n <= 1)
    return 0;
if (n == 2 || n == 3)
    return 1;
if (n % 2 == 0 || n % 3 == 0)
    return 0;
for (unsigned long long x = 5; x * x <= n; x += 6)
{
    if (n % x == 0 || n % (x + 2) == 0)
        return 0;
}
return 1;

Note that you don't use sqrt(N); you use i * i <= N. Or, if you must use sqrt(N), you calculate the value before the loop and use the calculated value, rounded up to the next integer (ceil() from <math.h>). At least, that was what my benchmarking a few years ago told me.

JFTR: transferring the code above into the code in the question, and timing p4 9872349901 yields the report that it is prime in an elapsed time of about 0.005 seconds (on an ordinary 2016 15" MacBook Pro with 2.7 GHz Intel Core i7 processor). I also tried 98723499017333 (adding 4 digits to the right end of the number, and getting a number of non-prime values before hitting on this one) which is reported as a prime in 0.044 seconds. The non-prime reports were quicker, of course.