Discussion :

[disedorgue]

Bon, voici déjà la méthode brut qui semble légèrement plus rapide que prime1.py:
Déjà le code:

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
$ cat prime6.py
#!/usr/bin/env python
# -*- coding: utf-8 -*-
 
import pyprimes
import time
 
a = 2
b = 3
c = 11
d = 31
valeur = 300000
objectif = 100
compte=1
chrono=[]
premiers=[]
 
chrono.append(time.clock())
for p in pyprimes.primes_below(objectif):
        if p in (a, b, c) or p >= d:
                premiers+=[p]
chrono.append(time.clock())
for x in premiers:
        for n in xrange(x, valeur,x):
                cnt=1
                for y in pyprimes.factors(n):
                        if y not in premiers or y < x :
                                cnt=0
                                break
                compte+=cnt
chrono.append(time.clock())
print valeur-compte
print chrono

Puis le benchmark:

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
$ time ./prime1.py
294261
[0.546, 19.155, 19.155]
 
real    0m19.370s
user    0m18.624s
sys     0m0.592s
$ time ./prime6.py
294261
[0.593, 0.593, 17.812]
 
real    0m17.995s
user    0m17.281s
sys     0m0.592s

Après comme je disais, on peut trouver le nombres de combinaisons possibles en réduisant le nombre de calcul, mais c'est plus complexe à programmer.
Ici, on a la liste des nombres premiers hors circuit, comme par exemple le 2, donc les nombres qui sont des puissance de 2 inférieurs a valeur sont aussi hors circuit.
Exemple:
valeur = 100
a=2
b=3
c=5
d=5
objectif=6

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
$ ./prime1.py
66
[0.577, 0.577, 0.577]

Donc ici, nos nombres premiers hors circuit sont [2,3,5]
Il suffit donc de trouver le nombre de puissance de 2 ou de 3 ou de 5 inférieur à 100, et pour ça, il suffit d'utiliser les logarithmes:
log2(100)=6.xxx
log3(100)=4.xxx
log5(100)=2.xxx
puis on calcul aussi:
log2(100/3)=log2(100)-log2(3)=5.xxx
log2(100/9)=log2(100)-(log2(3)+log2(3))=3.xxx
log2(100/27)=log2(100)-(log2(3)+log2(3)+log2(3))=1.xxx
log2(100/5)=log2(100)-log2(5)=4.xxx
log2(100/25)=log2(100)-(log2(5)+log2(5))=2
log2(100/15)=log2(100)-(log2(5)+log2(3))=2.xxx
log2(100/45)=log2(100)-(log2(5)+log2(3)+log2(3))=1.xxx
log3(100/5)=log3(100)-log3(5)=2.xxx
log3(100/25)=log3(100)-(log3(5)+log3(5))=1.xxx
Ensuite, il suffit d'additionner toutes les partie entière, ce qui donne ici 33 auquel on rajoute 1 (pour l'unité) ce qui nous fait 34
Et donc:
100-34=66

[Sve@r]

Désolé, ce pb ne m'amuse plus. Déjà on ne voit plus le PO et en plus c'est quand-même un pb assez débile.
Accessoirement, à 2h07, je dormais comme un ours.
Je suis quand-même impressionné par tes connaissances concernant certains raccourcis mathématiques pour éviter de calculer les facteurs. Ceci dit, je ne vois pas trop pourquoi tu préfères calculer log2(100) - log2(3) plutôt que log2(100/3). Est-ce que le temps gagné à ne pas faire la division est vraiment significatif comparé aux deux appels de la fonction log suivi d'une soustraction ?

[disedorgue]

Même si le problème par lui-même semble débile, dans la finalité, les résultats peuvent servir à trouver des pistes sur la factorisation des grands nombres ou généré de très grands nombres premiers (même si après, il y a d'autres problèmes un peu plus difficile à résoudre ).
Personnellement, ce problème m'a permit d'avoir une excuse pour aborder python .
Et pour répondre à ta question:
-on a déjà calculé log2(100).
-pour calculer log2(100/3), il nous suffit donc de calculer log2(3) et de le soustraire à log2(100) que l'on a déjà calculé.
De plus, si on regarde le calcul suivant, il s'agit de log2(100/9), donc du résultat précédent auquel on soustrait encore log2(3).
On aura donc moins de calcul de logarithme à faire et de simple soustractions au lieu de divisions...

Et l'autre intéret de montré la décomposition de log(a/b) en log(a)-log(b) permet de mieux voir comment j'obtiens cette liste de log(A/B):
par exemple, comment à un certain je sais que je dois calculer log2(100/15)