Overblog
Suivre ce blog
Editer l'article Administration Créer mon blog
20 juin 2011 1 20 /06 /juin /2011 13:43

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
 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...)

 

Partager cet article

Published by Pacman - dans Journal intime
commenter cet article

commentaires