Ouais, on revient aux choses sérieuses : EULER CHALLENGE N°3 !
http://projecteuler.net/index.php?section=problems
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
DISCLAIMER :
J'ai la flemme de m'inscrire sur le site, donc je ne prendrais même pas la peine de vérifier mes résultats
Ah, la décomposition en facteurs premiers... il n'y a pas grand chose de plus beau en ce monde !
1) La méthode brutale
Sous forme de questions successives :
Mon entier donné est-il divisible par un nombre entre 2 et lui-même ?
Ce diviseur est-il non divisible par un nombre entre 2 et lui-même (moins un) ?
=> Le plus grand de ceux-là, c'est le gagnant.
Allez :
SQL> WITH t AS (
2 SELECT level n
3 FROM DUAL
4 CONNECT BY level <= round(sqrt(600851475143))
5 )
6 SELECT case max(n) when 1 then 600851475143 else max(n) end
7 FROM t t1
8 WHERE mod(600851475143, n) = 0
9 AND NOT EXISTS (SELECT null
10 FROM t t2
11 WHERE mod(t1.n, t2.n) = 0
12 AND t2.n < round(sqrt(t1.n))
13 AND t2.n > 1
14 );
CASEMAX(N)WHEN1THEN600851475143ELSEMAX(N)END
--------------------------------------------
6857
2) La méthode pas géniale mais très légèrement moins naze
Ce qui est bien avec les diviseurs, c'est qu'ils s'emboîtent :
Si :
a = b * q
Et
b = c * q2
Alors d'une part c est un diviseur de a :
a = (c * q2) * q
Avec c < b
D'autre part, si a n'est pas divisible par n < b, alors b ne l'est pas non plus (ni c d'ailleurs).
Donc pour limiter la complexité moyenne de la décomposition, on peut travailler itérativement sur le quotient.
La démarche :
- On prend n = 600851475143
- On cherche le premier diviseur de n entre 2 et racine carrée de n
- Dès qu'on trouve un diviseur p, il est premier par construction (sinon, un autre aurait été diviseur avant lui)
- On prend le quotient n1 = n / p
- On recherche le premier diviseur de n1 entre p et racine carrée de n1
- Dès qu'on trouve un diviseur p1, il est premier par construction (sinon, un autre aurait été diviseur avant lui)
... on itère jusqu'à ce que le diviseur à tester soit supérieur à la racine du quotient.
A la fin, le quotient qu'on n'a pas réussi à diviser est le plus grand facteur premier !
SQL> SELECT n, p, m, n / p
2 FROM (
3 SELECT 600851475143 n, 2 p, round(sqrt(13195)) m
4 FROM DUAL
5 ) t
6 MODEL
7 DIMENSION BY (0 l)
8 MEASURES (n, p, m)
9 RULES
10 ITERATE(1000000) UNTIL (p[0] > m[0])
11 (
12 n[0] = CASE mod(n[0], p[0]) WHEN 0 THEN n[0] / p[0] ELSE n[0] END,
13 p[0] = CASE mod(n[0], p[0]) WHEN 0 THEN p[0] ELSE p[0] + 1 END,
14 m[0] = CASE mod(n[0], p[0]) WHEN 0 THEN round(sqrt(n[0] / p[0])) ELSE m[0] END
15 );
N P M N/P
---------- ---------- ---------- ----------
10086647 1471 83 6857
Tain, on dirait un exo de terminale...
Mais bon, j'ai vraiment pas trouvé plus joli pour chopper le plus grand facteur premier.
(Triste journée, en plus le temps est à chier...)
