Calculating prime factor of a huge number.
I've succesfully written some code that prints out the prime factors of integers. It works succesfully for small-ish integers, but my task is to calculate the largest prime factors of 600851475143. Here is my code, which works for the number 13195.
Code:
#include <stdio.h>
int isprime (int n);
int main()
{
int prime;
int i;
for (prime = 5; prime < 75; prime ++){
if (isprime(prime)&&13195%prime==0){
printf("A prime factor is %d.\n", prime);
}
}
getchar();
return 0;
}
int isprime (int n)
{
int i;
int boolean = 1;
for (i = 2; i < n/2; i++){
if (n%i==0){
boolean = 0;
}
}
return boolean;
}
Simply replacing the '13195' on line 10 with the huge integer 600851475143 doesn't work, as C doesn't like integers that big. I did a bit of research on how to represent numbers that large. I tried to represent it as a constant of type 'double' using:
Code:
#include <cmath>
double f = 6.00851475143*pow(10.0,11.0);
but that didn't work because of type differences, and it also failed when I typecasted f as an integer (it produced a large negative integer).
So is there any way to represent this huge integer that works, or must I find another method to work out the largest prime factor? I certainly can't think of another method :(