Factor 64 bit number in C

M. Gallant 03/10/2006
Tested on XP, Win2000 & Win95

Microsoft Win32 platform supports the Microsoft-specific C/C++ sized integer type __int64 data type (8 byte signed integer). The basic arithmetic operations are overloaded for this type. The win32 command-line application primefactors.exe provides factorization for numbers up to the 20 digit unsigned __int64 limit of:

18,446,744,073,709,551,615 = 2^64-1
The simplest way to use the application is to start it by double-clicking (or typing "primefactors" at a command prompt) and then type in any integer number (base 10) to be factored. The application also provides extended calculation capability with the following features: [Note: large listing ranges with file output requires considerable disk space (25 Mbytes per 1,000,000 numbers factored; see below)]

Performance:
Dell C800 Latitude P3 830 MHz, 512 Meg RAM Win2000
Single Number Performance example:
1111111111111111111 (19 digit "repunit" prime) takes ~ 1 minute.

File Generation Performance/Memory Requirements
Number RangeFull Factorization File SizePrimes-only File SizeExecution Time
1 - 20,000400 kb14 kb0.5 sec
1 - 200,0005 Mb130 kb4.5 sec
1 - 2,000,00050 Mb1.2 Mb60 sec

download primefactors.exe (136,320 bytes, digitally signed).


This win32 C application was compiled and linked with Visual Studio 2005 C++.