Overflow error in c to find prime factors of a twelve-digit number

user_13260495 0
Viewed 81

I want to solve this problem: https://projecteuler.net/problem=3 by this program, but I'm not sure its true way to use long long int.

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

int main(int argc, char *argv[]) {
    long long int result = factors(6051475143);
    printf("%lld", result); 
    return 0;
}

void factors(int number) {
    int factor[100000];
    int index = 0, i = 1;
    for (; i < number; i++) {
        if (number % i == 0) {
            factor[index] = i;
            index += 1;
        }
    }
    findprime(factor, 100000);
}

int findprime(int prime[], int size) {
    int i = 0, j;
    long long int latestprime;
    for(; i < size; i++) {
        if (prime[i] == 0)
            break;
        int is_prime = 1;
        for (j = 2; j < prime[i]; j++) {
            if (prime[i] % j == 0 && prime[i] != j) {   
                is_prime = 0;
                break;
            }
        }
        if (is_prime == 1)
            latestprime = prime[i];
    } 
    return latestprime;
}

If I try 10-digit number it works but when I try a 12-digit number it returns zero.

prime-factoring primes integer-overflow c
2 Answers

To solve this problem, you indeed need a type that is large enough to represent the number. unsigned long long is specified as having at least 64 value bits, which is 18446744073709551615.

Your program has undefined behavior, even for small numbers: result = factors(6051475143) does not reliably store anything useful as factors is defined as a void function and does not even have a return statement. It works by chance because the last statement, findprime(factor, 100000); leaves the return value of findprime in the register where main retrieves what it expects to be the int result of factors(), an return type inferred by the compiler from the lack of prototype.

To find the largest prime factor, you should try factors and reduce the number whenever you find one that divides it evenly.

Here is a modified version:

#include <stdio.h>

unsigned long long largest_factor(unsigned long long number) {
    unsigned long long p;
    if (number < 2)
        return number;
    for (p = 2; p * p <= number; p++) {
        while (number % p == 0) {
            number /= p;
        }
    }
    if (number == 1)
        return p;
    else
        return number;
}

int main(int argc, char *argv[]) {
    printf("%llu\n", largest_factor(6051475143)); 
    return 0;
}
user_45932670 
#include <stdio.h>
#include <stdlib.h>


int main() {

long long int result =factors(6051475143);
printf("%lld",result); 
return 0;
}

factors(long long int number)
{
    long int factor[1000000];
    long long int x;
    long int index=0,i=1;
    for(;i<800000; i++)
    {
        if (number%i==0)
        {
            factor[index] = i;
            index+=1;
        
        }
    }
    x = findprime(factor,index);
    return x;
}

int findprime(long int prime[],long int size)
{
    long int i = 0,j;
    long long int latestprime;
    for(;i<size;i++)
    {
        if (prime[i] == 0)
            break;
        int is_prime=1;
        for(j=2;j<prime[i];j++)
        {
            if (prime[i]%j==0 && prime[i]!=j)
            {   
                is_prime=0;
                break;
            }
        }
        if (is_prime==1)
            latestprime = prime[i];
    } 
    return latestprime;
}
user_122816670
Related