Mon aventure sur SPOJ et autres CodeForces

Bonjour, je me lance dans la programmation compétitive et je cré un poste pour vous demander de l’aide de manière régulière (plutôt que de polluer de posts identiques). De plus je souhaite publier des tribunes quand j’aurais quelque chose d’intéressant à dire du coup je me suis dis qu’un sujet serait aussi utile.

En tout cas me voici avec une première question et un premier problème :

Edit : Les règles de ce premier défi. L’input pour chaque test ce sont deux nombres : les deux bornes dans lesquels on doit chercher les nombres premiers. L’output ce sont tout les nombres premier entre ces deux bornes avec un nombre par ligne. Entre deux test on doit sauter une ligne

Je suis sur SPOJ et suis sur le deuxième problème (faut bien commencer). Je me prend la tête depuis déjà deux jours à cause des TLE (Time Limit Exceeded) quand ça fonctionne sur mon ordi. J’ai réussit à résoudre le problème et mon code s’exécute en 1.37s sur ideone mais en voici un autre : je n’ai pas la bonne réponse. Je sais que mon algorithme est bon d’après les tests que j’ai pu faire. Je n’arrive donc pas à comprendre pourquoi. Voici ma solution (si quelque chose n’est pas clair dîtes moi) :

 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
34
35
36
37
38
39
40
41
42
43
44
45
46

# Prime1 on SPOJ - SpheOnlineJudge.com

import sys
import math


def prime_sieve(start, end):
    nb = [False, False] + [True for i in range(2, end + 1)]  # 0 and 1 to False
    output = []
    i = 2

    while i < len(nb):
        if nb[i]:
            if i >= start:
                output.append(i)
            for j in range(i, len(nb), i):
                nb[j] = False
        while i < len(nb) and not nb[i]:
            i += 1
    return output


def main():
    nb_test = int(sys.stdin.readline())
    for e in range(nb_test):
        start, end = map(int, sys.stdin.readline().split(" "))

        primes = prime_sieve(2, math.ceil(math.sqrt(end)))

        if start == 1 or start == 2:
            print(2)
            start = 3

        for i in range(start, end + 1):
            is_prime = True
            for p in primes:
                if i % p == 0:
                    is_prime = False
                    break
            if is_prime:
                print(str(i))
        print()  # New line and each test case


if __name__ == '__main__':
    main()

En espérant que vous puissiez m’aider. Je passe par pure frustration

Bonjour et bienvenue dans ce monde de frustration, je te souhaite de continuer le plus loin possible malgré cela.

A tout hasard, est-ce que ce serait parce que tu fais un saut de ligne en trop à la fin ?

si tu veux ça peut faire un bon billet tu sais

Bonjour,

On voit que ton programme concerne les nombres premiers, mais tu ne nous dit pas ce qu’il est censé faire.

En l’occurrence, je ne comprends pas l’utilité de ta fonction main. Elle semble refaire le calcul pour savoir si un nombre est premier, alors que ça a déjà été calculé par prime_sieve…

@Entwanne Effectivement j’édit le message, j’étais un peu trop dans mon truc quand j’ai posté je pense

Merci pour vos encouragement !

L’input pour chaque test ce sont deux nombres : les deux bornes dans lesquels on doit chercher les nombres premiers. L’output ce sont tout les nombres premier entre ces deux bornes avec un nombre par ligne. Entre deux test on doit sauter une ligne

@Unidan Je viens d’essayer et ce n’est pas ça :/

Oui, donc tu devrais juste avoir un appel à prime_sieve avec les deux bornes, et afficher chaque élément de la liste résultante sur une nouvelle ligne.

Pourquoi recalculer si les nombres sont premiers dans la fonction main ?

Initialement je faisais comme ça mais je me prend un TLE (Time Limit Exceeded). Les bornes vont jusqu’à 10^{9 avec un différence de 10}6 entre le min et le max. Du coup ce que je fais c’est que je calcul tout les nombres premiers jusqu’à la racine du max avec le crible (sieve) et ensuite je regarde si les nombres entre le min et le max (start et end dans mon code) sont premier dans le main.

Rien à voir : Je sais qu’une amélioration possible serait de sauvegarder le tableau des premiers déjà calculés d’une itération à l’autre ce qui éviterais parfois beaucoup de calculs.

Ici, tu as nb_test = .... je ne sais pas combien, mais disons 50 (c’est combien pour le test ?. Et donc tu lances une procédure prime_sieve(a,b) 50 fois, avec des paramètres quasiment identique. Si tu la lançais une seule fois, avec comme paramètre (2, max(b)), j’ai l’impression que tu ferais une grosse amélioration.

Mais peut-être que c’est ce que tu envisages dans ton dernier message.

Je ne sais pas si tu peux mesurer le temps consommé par cette procédure ?

Mmh… J’ai dû changer un truc et j’avais pas fait gaffe. Je regarderais demain. Merci

@Elegance C’est effectivement ce dont je parle. C’est ce que j’avais initialement fait mais c’est plus lent. En fait générer tout les nombres premiers avec le crible d’erathostène est beaucoup trop lent. D’où le fait de les générer jusqu’à la racine carré du max. Ce que je devrais faire serait de d’abord générer les premiers jusqu’à la racine du max et ensuite faire ma procédure. Je le ferais une fois que j’aurais corrigé mon problème de mauvaise réponse.

Mais tu dois de toute manière tous les générer pour les afficher, je ne comprends pas. Tu as peut-être juste besoin d’un cache dans prime_sieve ?

En fait j’économise tout les nombres entre la racine du max et le min. Sur les grands nombres l’économie est importante

Mais c’est dans prime_sieve que tu pourrais faire ces économies.

C’est à dire ? En ne le lançant qu’une fois dans le cas maximum ?

C’est à dire que tu es obligé de générer un crible complet pour l’afficher (afin d’y effacer les multiples des nombres premiers), mais ta fonction prime_sieve n’est pas obligée d’itérer jusque end, elle peut s’arrêter à sqrt(end).

En fait j’appel prime_sieve avec sqrt(end) :

1

primes = prime_sieve(2, math.ceil(math.sqrt(end)))

En fait le sieve me permet d’avoir tout les premiers qui me permettront de vérifier si les nombres en entrée sont premier. Du coup j’ai besoin d’aller jusqu’au bout, non ?

Non mais j’ai vu ça. Sauf que tu utilises le résultat de prime_sieve pour recalculer les nombres premiers entre start et end.

Alors que tu aurais pu appeler directement la fonction avec start et end, et faire en sorte que prime_sieve limite d’elle-même sa recherche à partir de sqrt(end) (tout en retournant tous les premiers entre start et end).

Je n’ai pas testé ton code, mais quelque chose me gène sur cette portion de code :

1
2
3
4
5
6
7
8
9

def main():
    nb_test = int(sys.stdin.readline())
    for e in range(nb_test):
        start, end = map(int, sys.stdin.readline().split(" "))

        # partie du code qui calcule beaucoup
        primes = prime_sieve(2, math.ceil(math.sqrt(end)))

        # suite du code

Tu exécutes plusieurs fois inutilement prime_sieve (qui est consommateur) puisqu’il se trouve ici dans une boucle qui peut aller jusqu’à 10 itérations.

Si on prend un cas un peu chaud :

1
2
3
4

3
20 100
60 100
20 40

Ta fonction prime_sieve va passer sur l’intervalle [20 - 100] et repasser sur l’intervalle [60 - 100] puis sur le [20 - 40]. Alors que si tu avais mis en mémoire les résultats obtenus sur le premier intervalle, ça t’aurait permis de diviser ton temps de calcul par deux.

@Entwanne D’accord, j’avais pas compris. Du coup c’est un choix délibéré. Je voulais garder "prime_sieve" pour ce que c’est : l’algorithme du crible d’eratosthène. J’aurais pu effectivement ne pas mettre dans le main le reste mais vu la longueur du code je ne me suis pa embêter.

@Firm1 C’est effectivement une amélioration que je dois faire. J’ai pas cherché à faire au mieux, une fois que le temps était correct je me suis rendu compte que ma réponse était fausse et j’ai pas eu le temps de corriger encore.

J’ai l’impression que tu ne lis pas ce que j’écris. Tu viens avec tes idées préconçues, et tu refuses d’en sortir.

Le programme que tu dois implémenter EST le crible d’Eratosthène. Il doit retourner tous les nombres premiers entre deux bornes. Donc l’optimisation permettant de ne pas rechercher après la racine carrée de la borne max, tu peux l’implémenter dans prime_sieve !

Ainsi, main n’aura plus qu’à itérer sur les listes retournées par les différents appels à prime_sieve et en afficher les éléments.

(et tu peux mettre en cache les résultats)

@entwanne, tu es sûr que ce que tu proposes n’est pas au moins linéaire en la valeur de la borne supérieure de l’intervalle ?

[Le programme qu’il doit implémenter n’est pas juste le crible d’Erathosthène naïf. Par exemple, si on veut énumérer tous les multiples de $2$, on devrait compter de 2 en 2 jusqu’à la borne sup ? La méthode que @Ricocotam propose consiste à dire qu’un nombre $n$ est premier ssi. il n’est divisible par aucun premier positif inférieur à $\sqrt{n}$. C’est un raffinement de la méthode naïve qui dit qu’un nombre est premier ssi. il n’est divisible par aucun entier positif non trivial inférieur à $\sqrt{n}$. En gros l’amélioration permet de gagner un facteur $\log n/2$ (théorème des nombres premiers). Il y a deux étapes dans ce qu’il fait sur $[a,b]$ : d’abord il génère les nombres premiers inférieurs à $\sqrt{\text{b}}$, puis il teste les divisibilités de chaque entier de $[a,b]$ avec chacun des éléments de la liste. En fait, on peut faire mieux que ça, mais je n’ai pas l’impression que tes remarques y mènent.]