Obtenir une liste de nombres sans carré

Question

Une façon d'obtenir cela est pour les nombres naturels (1, , n ) nous factorisons chacun d'entre eux et voyons s'ils ont des facteurs premiers répétés, mais cela prendrait beaucoup de temps pour les grandes entreprises. n . Y a-t-il un meilleur moyen d'obtenir les nombres sans carré de 1,.., n ?

Answer 1

En cherchant un peu sur Google, j'ai trouvé ceci page où un programme J est expliqué. A part la syntaxe complexe, l'algorithme permet de vérifier si un nombre est sans carré ou non :

• générer une liste de PS à carré parfait,

• prenez votre nombre N et divisez-le par les nombres de la liste PS

• s'il n'y a qu'un seul nombre entier dans la liste, alors N est sans carré

Vous pouvez implémenter l'algorithme dans votre langage préféré et l'itérer sur n'importe quel nombre de 1 à n.

Answer 2

http://www.marmet.org/louis/sqfgap/

Consultez la section "Algorithme de base : le tamis d'Eratosthène", c'est ce qu'a suggéré Armen. La section suivante est "Améliorations de l'algorithme".

De plus, pour info, le Moebius et les nombres sans carré sont liés.

Answer 3

J'ai trouvé un meilleur algorithme pour calculer le nombre de nombres sans carré dans un intervalle tel que [n,m]. On peut obtenir des nombres premiers inférieurs à sqrt(m) Nous devrions alors soustraire les multiples du carré de ces nombres premiers, puis ajouter les multiples du produit de chaque paire de nombres premiers inférieurs à m, puis soustraire l'arbre, puis ajouter quatre..... Enfin, nous obtiendrons la réponse. Il est certain que cela fonctionne en O(sqrt(m)) .

Answer 4

import math
def squarefree(n):
    t=round(math.sqrt(n))
    if n<2:
       return True
    if t*t==n:
       return False
    if t<=2:
       return True
    for i in range(2,t):
        if n%(i*i)==0:
           return False
        else:
           return True