Получение списка номеров без квадратов

Question

Один из способов получить это для натуральных чисел (1, .., n ), которые мы разлагаем на части и видим, есть ли у них повторяющиеся простые множители, но для больших потребуется много времени п .Так есть ли лучший способ получить числа без квадратов от 1, .., n ?

Answer 1

Вы можете использовать модифицированную версию Eratosthenes Sieve:

Взять массив bool 1 .. n ;

Предварительно вычислить все квадраты, которые меньше n;это O (sqrt (N));

Для каждого квадрата и его кратных сделайте запись массива bool ложной ...

Answer 2

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

Не существует известного алгоритма полиномиального времени для распознавания целых чисел без квадратов или для вычисления целой части без квадратов.На самом деле, эта проблема может быть не проще, чем общая проблема факторизации целочисленных значений (очевидно, если целое число можно полностью разложить на множители, то оно не содержит квадратов, если оно не содержит дублирующихся факторов).Эта проблема является важной нерешенной проблемой в теории чисел, поскольку вычисление кольца целых чисел поля алгебраических чисел сводится к вычислению квадратичной части целого числа (Lenstra 1992, Pohst and Zassenhaus 1997).

Answer 3

Самое прямое, что приходит в голову, - перечислить простые числа до n и выбрать не более одного из каждого. Это не легко для больших n (например, вот один алгоритм ), но я не уверен, что эта проблема тоже.

Answer 4

Один из способов сделать это - использовать сито, подобное Эратосфену.

@ Will_Ness написал «быстрое» простое сито в 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

Сбез особых усилий, это можно использовать для извлечения целых чисел без квадратов, используя postponed_sieve () в качестве основы для просеивания на как можно меньшее число квадратов:

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

Это довольно быстро, выбрасываяПервый миллион за 0,8 с на моем ноутбуке.

Неудивительно, что это показывает, что это фактически та же проблема, что и просеивание простых чисел, но с гораздо большей плотностью.

Answer 5

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

Answer 6

Я нашел лучший алгоритм для вычисления количества свободных от квадратов чисел в интервале, например [n, m].Мы можем получить простое число, которое меньше чем sqrt(m), тогда мы должны минус кратные квадраты этих простых чисел, затем плюс кратные произведения каждого двух простых чисел меньше m, затем минус дерево, затем плюс четыре .... в последниймы получим ответ.Конечно, он работает в O(sqrt(m)).

Answer 7

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

Ознакомьтесь с разделом «Основной алгоритм: сито Эратосфена», который предложил Армен.Следующий раздел «Улучшения алгоритма».

Кроме того, FWIW, функция Мебиуса и числа без квадратов связаны между собой.

Answer 8

Погуглив немного, я нашел эту страницу , где объясняется J-программа. Являясь частью сложного синтаксиса, алгоритм позволяет проверить, является ли число свободным от квадрата или нет:

• сгенерировать список совершенных квадратов PS,

• возьмите свое число N и разделите его на цифры в списке PS

• если в списке только 1 целое число, тогда N не имеет квадратов

Вы можете реализовать алгоритм на предпочитаемом вами языке и повторять его по любому числу от 1 до n.

Answer 9

Вам, вероятно, стоит заглянуть в сито Аткина .Конечно, это исключает все не простые числа (не только идеальные квадраты), поэтому может потребоваться больше работы, чем вам нужно.