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 :(

Depending on what compiler you are using, you may be limited to 32-bit unsigned, which is a shade over 4000000000. If your computer supports 64-bit integers, then you can get MUCH larger numbers. Microsoft compilers have a "_int64" type, whilst gcc uses the more standard form of "long long int".

--
Mats

I tried:

Code:

---

__int64 f = 600851475143;

---

I get a compiler error saying 'integer constant is too large for "long" type'. Same for long long int.

I'm using Dev-C++, I assume that int64 and long long int aren't supported on this compiler?

Quote:

---

Originally Posted by Bakster

I tried:

Code:

---

__int64 f = 600851475143;

---

I get a compiler error saying 'integer constant is too large for "long" type'. Same for long long int.

I'm using Dev-C++, I assume that int64 and long long int aren't supported on this compiler?

---

They are, but you need to post-fix the number with LL to make it a "long long"(since it's a GCC based compiler, long long is fine, but you need to use "%I64d" to let printf display the number).

--
Mats

Quote:

---

Originally Posted by matsp

They are, but you need to post-fix the number with LL to make it a "long long"(since it's a GCC based compiler, long long is fine, but you need to use "%I64d" to let printf display the number).

--
Mats

---

It works now, thanks a lot :)

Tsk tsk, this is a project euler problem! I wonder what you do if you don't have a 64-bit machine...

Quote:

---

Originally Posted by neandrake

Tsk tsk, this is a project euler problem! I wonder what you do if you don't have a 64-bit machine...

---

You need a more powerful computer, like this one :)

http://cgi.ebay.co.uk/TWO-OLD-RULER-...3A2|240%3A1318

And one of these:-

http://cgi.ebay.co.uk/Maths-Basics-A...3A2|240%3A1318

Quote:

---

Originally Posted by neandrake

Tsk tsk, this is a project euler problem! I wonder what you do if you don't have a 64-bit machine...

---

I think basicaly you will have to print the numbers into strings, which can be as long as you like and then impliment a routine to do long hand division, particularly if the denominator is greater than max_int. If it is less than max_int then you can probably use a faster method using 'normal' computer division, however I am not sure if you can get the correct remainder with that. I don't think you can 'split' the denomminator into a shorter numbers, at least I can't think of how to do it, maybe there is a method.

I would expect there must be rountines done to do such 'stuff' already written.

Plenty of languages other than C support arbitrary precision arithmetic natively, and project euler doesn't require the use of C. If you need/want to use C and don't have C99 long long support (you don't necessarily need a 64 bit machine), there's always libgmp (The GNU MP Bignum Library).

You can use digits in int arrays, you just have to know your base 10 number line, and how it works.

esbo - lol ;p

cwr - or you can write your own library (which was my point). I am actually working on a personal C library to store 8 digits inside of a 32-bit integer. I have it working, but have been too lazy to implement arithmetic functions for actually using them. Some day I will get around to it. Thank you for bringing up my point.

A good bignum library actually doesn't use strings to represent numbers. I once had to write a bignum library in ML. I used an array of ints to store the digits of a number in a large base, say sqrt(INT_MAX). This way, you can use ordinary arithmetics on digits (and probably won't use many digits... every int value fits into two digits this way). The string part is only needed to convert the number from and to a human readable form.

Greets,
Philip

Snafuist - Curious, how are you storing numbers in base sqrt(INT_MAX)?

Quote:

---

Originally Posted by Snafuist

how are you storing numbers in base sqrt(INT_MAX)?

---

It was stated in the earlier part of the sentence: "an array of ints".

Or if the question is "INT_MAX" isn't a perfect square, that is true; presumably the base was 2^(n/2) if int had n bits in it.

For Euler challenges requiring large numbers I'd really recommend a language that supports them natively, e.g Python (learning the basics, essentially programming in C-style, should not be too hard).

It also sort of seems to me that the algorithm might be not quite as efficient as possible (checking is_prime means trying to divide with the same values over and over).

Think about it.

For example, the prime factors of 38962 are 2, 7, 11, 11 and 23. The largest prime factor is 23. Do you really need to check all (odd) numbers all the way up to sqrt(38962) = 197 ? (It should be possible to find the prime factors using modulus around 13 times, not 98 * some_n times.)