Obtenir une liste des numéros gratuits carrés

Question

Une façon d'obtenir c'est pour les nombres naturels (1, .., n ) nous factoriser chacun et voir s'ils ont des facteurs premiers répétés, mais cela prendrait beaucoup de temps pour grand n . Donc, il y a une meilleure façon d'obtenir les numéros sans carrés de 1, .., n

Answer 1

Vous pouvez utiliser la version modifiée de Eratosthène Sieve:

Prenez un tableau de bool 1 .. n

Precalc tous les carrés qui sont inférieurs à n; que de O (sqrt (N));

Pour chaque carré et ses multiples font l'entrée de gamme bool faux ...

Answer 2

De http://mathworld.wolfram.com/Squarefree.html

Il n'y a pas de temps polynomiale connu algorithme de reconnaissance quadratfrei des nombres entiers ou pour le calcul de la quadratfrei partie d'un entier. Dans fait, ce problème peut être pas plus facile que le problème général de nombre entier factorisation (évidemment, si un entier peut être pris en compte complètement, est quadratfrei ssi il ne contient pas facteurs dupliqués). Ce problème est un problème non résolu important dans la théorie des nombres, car le calcul du anneau des entiers d'un algébrique champ de numéro est réductible à l'informatique la partie quadratfrei d'un nombre entier (Lenstra 1992, Pohst et Zassenhaus 1997).

Answer 3

La chose la plus directe qui vient à l'esprit est à la liste des nombres premiers jusqu'à n et sélectionnez au plus un de chaque. Ce n'est pas facile pour n grand (par exemple est ici un algorithme ), mais je ne suis pas sûr que ce problème est soit.

Answer 4

Une façon de le faire est d'utiliser un tamis, similaire à Eratosthène.

@Will_Ness a écrit un "rapide" tamis premier comme suit en Python.

from itertools import count
                                         # ideone.com/
def postponed_sieve():                   # postponed sieve, by Will Ness      
    yield 2; yield 3; yield 5; yield 7;  # original code David Eppstein, 
    sieve = {}                           # Alex Martelli, ActiveState Recipe 2002
    ps = postponed_sieve()               # a separate base Primes Supply:
    p = next(ps) and next(ps)            # (3) a Prime to add to dict
    q = p*p                              # (9) its sQuare 
    for c in count(9,2):                 # the Candidate
        if c in sieve:               # c's a multiple of some base prime
            s = sieve.pop(c)         #     i.e. a composite ; or
        elif c < q:  
            yield c                  # a prime
            continue              
        else:   # (c==q):            # or the next base prime's square:
            s=count(q+2*p,2*p)       #    (9+6, by 6 : 15,21,27,33,...)
            p=next(ps)               #    (5)
            q=p*p                    #    (25)
        for m in s:                  # the next multiple 
            if m not in sieve:       # no duplicates
                 break
         sieve[m] = s                # original test entry: ideone.com/WFv4f

Avec un peu d'effort, cela peut être utilisé pour sortir des entiers carrés libres, en utilisant le postponed_sieve () pour servir de base à tamiser par quelques carrés que possible:

def squarefree():                   # modified sieve of Will Ness
    yield 1; yield 2; yield 3;      # original code David Eppstein,
    sieve = {}                      # Alex Martelli, ActiveState Recipe 2002
    ps = postponed_sieve()          # a base Primes Supply:
    p = next(ps)                    # (2) 
    q = p*p                         # (4)
    for c in count(4):              # the Candidate
        if c in sieve:              # c's a multiple of some base square
            s = sieve.pop(c)        #     i.e. not square-free ; or
        elif c < q:  
            yield c                 # square-free
            continue              
        else:   # (c==q):           # or the next base prime's square:
            s=count(2*q,q)          #    (4+4, by 4 : 8,12,16,20...)
            p=next(ps)              #    (3)
            q=p*p                   #    (9)
        for m in s:                 # the next multiple 
            if m not in sieve:      # no duplicates
                break
        sieve[m] = s

Il est assez rapide, coups de pied le premier million dans environ .8s sur mon ordinateur portable.

Sans surprise, cela montre que ce qui est effectivement le même problème que les nombres premiers tamiser, mais avec une densité beaucoup de plus.

Answer 5

Vous devriez probablement dans le tamis de Atkin. Bien sûr, cela élimine tous les non-nombres premiers (et pas seulement des carrés parfaits) de sorte qu'il pourrait être plus de travail que vous avez besoin.

Answer 6

googler un peu, je l'ai trouvé cette où un programme de J est expliqué. Une partie de la syntaxe complexe, l'algorithme permet de vérifier si un nombre est exempt de carré ou non:

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

• prendre votre numéro N et le diviser par les numéros de la liste PS

• s'il n'y a que 1 nombre entier dans la liste, alors N est sans place

Vous pourriez mettre en œuvre l'algorithme dans votre langue préférée et itérer sur un nombre quelconque de 1 à n.

Answer 7

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

Consultez la section « algorithme de base: le tamis d'Eratosthène », ce qui est suggéré Armen. La section suivante est « Amélioration de l'algorithme ».

En outre, FWIW, Mœbius fonction et numéros gratuits carrés sont liés .

Answer 8

J'ai trouvé un meilleur algorithme pour calculer le nombre de numéros sans carrés dans un intervalle tel que [n, m]. Nous pouvons prime que moins de sqrt(m), alors nous devrions moins les multiples de ces premier carré de puis plus les multiples du produit de chacun deux nombres premiers inférieurs m, puis arbre moins, puis plus quatre .... au dernier nous allons obtenir la réponse. Certes, il court dans O(sqrt(m)).

Answer 9

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