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

Vous pourriez utiliser la version modifiée d'Eratosthenes Sieve :

Prenez un tableau de bools 1.. n ;

Précalculez tous les carrés inférieurs à n ; c'est O(sqrt(N)) ;

Pour chaque carré et ses multiples, rend l'entrée du tableau bool fausse...

Answer 2

La solution la plus directe qui me vient à l'esprit est d'énumérer les nombres premiers jusqu'à n et de sélectionner au maximum un de chacun. Ce n'est pas facile pour les grands nombres n (par ex. Voici un algorithme ), mais je ne suis pas sûr que ce problème le soit non plus.

Answer 3

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

Il n'y a pas de temps polynomial connu pour reconnaître les entiers sans carré ou pour calculer la partie partie sans carré d'un nombre entier. En En fait, ce problème n'est peut-être pas plus facile que le problème général de la factorisation factorisation des entiers (évidemment, si un entier peut être factorisé complètement, est sans carré s'il ne contient pas facteurs dupliqués). Ce problème est un important problème non résolu en théorie des nombres car le calcul de l'anneau anneau d'entiers d'un champ de nombres algébriques algébrique est réductible au calcul de la partie sans carré d'un entier (Lenstra, 1992 ; Pohst et Zassenhaus, 1997). 1997).

Answer 4

Une façon de procéder est d'utiliser un tamis, semblable à celui d'Eratosthène.

@Will_Ness a écrit un tamis primaire "rapide" 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 sans carrés, en utilisant le postponed_sieve() pour servir de base au tamisage par le moins de carrés 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

C'est assez rapide, il envoie le premier million en environ 0,8 s sur mon ordinateur portable.

Sans surprise, cela montre qu'il s'agit effectivement du même problème que le tamisage des primes, mais avec une densité beaucoup plus grande.

Answer 5

Vous devriez probablement vous pencher sur le tamis d'Atkin . Bien sûr, cela élimine tous les non-primes (et pas seulement les carrés parfaits), ce qui peut représenter plus de travail que nécessaire.