# Calculating prime factor of a huge number.

Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last
• 01-29-2009
Bakster
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 :(
• 01-29-2009
matsp
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
• 01-29-2009
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?
• 01-29-2009
matsp
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
• 01-29-2009
Bakster
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 :)
• 01-29-2009
neandrake
Tsk tsk, this is a project euler problem! I wonder what you do if you don't have a 64-bit machine...
• 01-29-2009
esbo
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
• 01-29-2009
esbo
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.
• 01-29-2009
cwr
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).
• 01-30-2009
You can use digits in int arrays, you just have to know your base 10 number line, and how it works.
• 02-18-2009
neandrake
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.
• 02-19-2009
Snafuist
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
• 02-20-2009
neandrake
Snafuist - Curious, how are you storing numbers in base sqrt(INT_MAX)?
• 02-20-2009
laserlight
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".
• 02-20-2009
tabstop
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.
Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last