04/11/2008
Project Euler : Solution au problème 3, en C
Toujours dans la série des problèmes du Project Euler, voici ma solution au problème 3, en C toujours, mais qui m'embête un peu parce que je sors du contexte ANSI/ISO C en utilisant une librairie GNU pour la manipulation de nombre atrocement grand.
D'ailleurs au passage, n'ayant pas d'expérience en manipulation de big-integers, je suis preneur de toute sagesse sur le sujet.
/* 2008/11/01 - euler3.c
* Solution au Probleme 3 de Project Euler
* http://projecteuler.net/index.php?section=problems&id=3
* Jean Karim Bockstael - jkb@jkbockstael.be
*/
#include <stdio.h>
#include <imath.h>
#define MAXPRIMES 200000
int findprimes(int primes[], unsigned long long maxvalue) {
primes[0]=2; /* le premier premier */
int numfound=1;
int i,j;
int pri; /* pri=0 si divisible */
for (i=3; i<maxvalue; i+=2) {
pri=1; /* jusqu'a preuve du contraire */
for (j=0; j<numfound; j++) {
if ((i%primes[j])==0) {
pri=0;
break;
}
}
if (pri) {
primes[numfound++]=i;
}
}
return numfound;
}
int euler3(unsigned long long n) {
int foundprimes[MAXPRIMES];
int numfound=findprimes(foundprimes,lsqrt64(n));
int i;
for (i=numfound; i>=0; i--) {
if ((n%foundprimes[i])==0) {
break;
}
}
return i==-1 ? i : foundprimes[i];
}
int main(int argc, char** argv) {
printf("%i\n",euler3(600851475143ull)); /* Y'a pas encore plus grand? */
return 0;
}