C Code to check whether a number is a product of primes or not does not work for great numbers-CodePudding

I developed this C Code Below that executes two functions. The first one, modozero, finds the next prime number, and I think it's working properly. However, the function modoum, which is supposed to find if a number is the product of two prime numbers is not working for large numbers and I don't really know how to work on that. I think the problem has got to do with Time of Execution, but I'm not sure.

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

long int modozero(long int num);
long int primeverification(long int num);
long int modoum(long int num);

int main(int argc, char *argv[]) {
    long int modo, num;

    modo = atoi(argv[1]);
    num = atoi(argv[2]);

    if (!modo)
        modozero(num);
    else
        modoum(num);

    return 0;
}

long int primeverification(long int num) {
    long int i, remainder;
    for (i = 2; i <= num / 2; i  ) {
        remainder = num % i;
        if (!remainder)
            return 0;
    }
    return 1;
}

long int modozero(long int num) {
    long int isprime = 0;
    while (!isprime) {
        num  ;

        isprime = primeverification(num);
        printf("is prime %ld \n", isprime);
    }
    printf("%ld \n", num);
    return num;
}

long int modoum(long int num) {
    long int i, j, remainder;

    for (i = 2; i <= num / 2; i  ) {
        if (primeverification(i)) {
            remainder = num % i;

            if (!remainder) {
                j = num / i;
                if (primeverification(j)) {
                    printf("%ld %ld", i, j);
                    return 0;
                }
            }
        }
    }
    return 0;
}

Examples of executions:

$ ./prime 1 6
2 3

$ ./prime 1 1000
#No print since 1000 is not a product of primes

$ ./prime 1 908118221
30133 30137

$ ./prime 1 908118220
#When I do this imput, the program doesn't finish the execution
#Weird that it doesn't work for this number that we know that is not a product of primes and it is smaller than the previous number we tested

CodePudding user response：

The main reason your program does not work with large numbers is you use atoi to convert the command line arguments to numbers, and this function has undefined behavior for representations of number beyond the range of type int. You should use strtol():

modo = strtol(argv[1], NULL, 0);
num = strtol(argv[2], NULL, 0);

And you should check for conversion errors.

Here is a modified version of the main function:

#include <errno.h>
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[]) {
    long int modo, num;
    char *p;

    errno = 0;
    modo = strtol(argv[1], &p, 0);
    if (p == argv[1] || *p != '\0' || errno != 0) {
        fprintf(stderr, "conversion error: %s\n", argv[1]);
        return 1;
    }

    errno = 0;
    num = strtol(argv[2], &p, 0);
    if (p == argv[2] || *p != '\0' || errno != 0) {
        fprintf(stderr, "conversion error: %s\n", argv[2]);
        return 1;
    }

    if (modo == 0)
        modozero(num);
    else
        modoum(num);

    return 0;
}

Furthermore, the function primeverification is too slow for large numbers: if the number is prime, it will iterate num / 2 times, which may take a long time. You should stop at the square root of num, which can be tested this way:

long int primeverification(long int num) {
    long int i, remainder;

    if (num <= 1) {
        return 0;
    }
    if (num % 2 == 0) {
        /* the only even prime number is 2 */
        return num == 2;
    }
    /* only test odd divisors from here */
    for (i = 3; i <= num / i; i  = 2) {
        remainder = num % i;
        if (!remainder)
            return 0;
    }
    return 1;
}

You should also remove the printf("is prime %ld \n", isprime); in function modozero.

In function modoum, it would be more efficient to test i for primeness only if i divides num evenly, and stopping at the square root of num is also recommended (because one of the prime factors must be <= num):

long int modoum(long int num) {
    long int i, j, remainder;

    /* test 2, then 3, 5, 7, etc. */
    for (i = 2; i <= num / i; i  = 1   (i & 1)) {
        remainder = num % i;
        if (!remainder && primeverification(i)) {
            j = num / i;
            if (primeverification(j)) {
                printf("%ld = %ld * %ld\n", num, i, j);
                return 0;
            }
        }
    }
    return 0;
}

Here is a modified version of the full program:

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

long int primeverification(long int num) {
    long int i, remainder;

    if (num <= 1) {
        return 0;
    }
    if (num % 2 == 0) {
        /* the only even prime number is 2 */
        return num == 2;
    }
    /* only test odd divisors from here */
    for (i = 3; i <= num / i; i  = 2) {
        remainder = num % i;
        if (!remainder)
            return 0;
    }
    return 1;
}

// output and return the next prime
long int modozero(long int start) {
    long int num = start;
    while (num < LONG_MAX) {
        num  ;
        if (primeverification(num)) {
            printf("%ld\n", num);
            return num;
        }
    }
    printf("no primes larger than %ld\n", start);
    return -1;
}

long int modoum(long int num) {
    long int i, j, remainder;

    /* test 2, then 3, 5, 7, etc. */
    for (i = 2; i <= num / i; i  = 1   (i & 1)) {
        remainder = num % i;
        if (!remainder && primeverification(i)) {
            j = num / i;
            if (primeverification(j)) {
                printf("%ld = %ld * %ld\n", num, i, j);
                return 0;
            }
        }
    }
    return 0;
}

long int convert(const char *s) {
    char *p;
    long int num;

    errno = 0;
    num = strtol(s, &p, 0);
    if (p == s || *p != '\0' || errno != 0) {
        fprintf(stderr, "conversion error: %s\n", s);
        exit(1);
    }
    return num;
}

int main(int argc, char *argv[]) {
    long int modo, num;

    if (argc < 3) {
        fprintf(stderr, "missing arguments\n");
        return 1;
    }
    modo = convert(argv[1]);
    num = convert(argv[2]);

    if (modo == 0)
        modozero(num);
    else
        modoum(num);

    return 0;
}