Получение списка свободных от квадратов чисел
Один из способов получить это для натуральных чисел (1,..,n), мы разложим их по частям и посмотрим, есть ли у них повторяющиеся простые множители, но для больших n это займет много времени. Так есть ли лучший способ получить числа без квадратов от 1,..,n?
10 ответов
Вы можете использовать модифицированную версию Eratosthenes Sieve:
Возьмите массив bool 1..n;
Предварительно вычислить все квадраты, которые меньше n; это O(sqrt(N));
Для каждого квадрата и его кратных значений сделайте запись массива bool ложной...
С http://mathworld.wolfram.com/Squarefree.html
Не существует известного алгоритма полиномиального времени для распознавания целых чисел без квадратов или для вычисления части целых чисел без квадратов. Фактически, эта проблема может быть не проще, чем общая проблема факторизации целых чисел (очевидно, если целое число может быть полностью разложено на множители, то оно не содержит квадратов, если оно не содержит дублирующихся факторов). Эта проблема является важной нерешенной проблемой в теории чисел, поскольку вычисление кольца целых чисел поля алгебраических чисел сводится к вычислению квадратичной части целого числа (Lenstra 1992, Pohst and Zassenhaus 1997).
Самое прямое, что приходит на ум, - перечислить простые числа до n и выбрать не более одного из каждого. Это не легко для больших n (например, вот один алгоритм), но я не уверен, что эта проблема тоже.
Один из способов сделать это - использовать сито, подобное Эратосфену.
@Will_Ness написал "быстрое" простое сито в Python следующим образом.
from itertools import count
# ideone.com/aVndFM
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 на моем ноутбуке.
Неудивительно, что это показывает, что это фактически та же проблема, что и просеивание простых чисел, но с гораздо большей плотностью.
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
Вам, вероятно, стоит заглянуть в сито Аткина. Конечно, это устраняет все не простые числа (не только идеальные квадраты), так что это может быть больше работы, чем вам нужно.
http://www.marmet.org/louis/sqfgap/
Ознакомьтесь с разделом "Основной алгоритм: сито Эратосфена", который предложил Армен. Следующий раздел - "Улучшения алгоритма".
Кроме того, FWIW, функция Мёбиуса и числа без квадратов связаны между собой.
Согласно решению @Armen, мы можем использовать модифицированную форму Решета Эратосфена. Вот реализация C++ без использования динамических массивов:
vector<unsigned> squarefree_eratosthenes(unsigned n) {
unsigned count = n - 1;
bool squarefree[n + 1];
memset(squarefree, 1, sizeof(squarefree));
for (int p = 2; p*p <= n; p++) {
if (squarefree[p*p]) {
for (int i = p*p; i <= n; i += p*p) {
count -= squarefree[i];
squarefree[i] = false;
}
}
}
vector<unsigned> sieved(count,0);
count = 0;
for (int p = 2; p <= n; p++) {
if (squarefree[p]) {
sieved[count] = p;
count++;
}
}
return sieved;
}
Я нашел лучший алгоритм для вычисления количества свободных от квадратов чисел в интервале, например [n,m]. Мы можем получить премьер, что меньше, чем sqrt(m), тогда мы должны минус кратные квадрата этих простых чисел, затем плюс кратные произведения каждого двух простых чисел меньше m, затем минус дерево, а затем плюс четыре.... в конце мы получим ответ. Конечно, это работает в O(sqrt(m)),
Погуглив немного, я нашел эту страницу, где объясняется J-программа. Являясь частью сложного синтаксиса, алгоритм позволяет проверить, является ли число свободным от квадратов или нет:
сформировать список идеальных квадратных PS,
возьмите свое число N и разделите его на числа в списке PS
- если в списке всего 1 целое число, то N не содержит квадратов
Вы можете реализовать алгоритм на предпочитаемом вами языке и повторять его по любому числу от 1 до n.