P–给定范围内的平滑数字
给定多个范围【L，R】和一个素数 P，我们需要在给定的单个范围内找到所有P-光滑数 。
什么是 P–光滑数？ 如果一个整数的最大质因数< = p. 1(被 OEIS 认为)对于任何可能的 P 值都是 P-光滑数，因为它没有任何质因数。
示例:
Input : p = 7
ranges[] = {[1, 17], [10, 25]}
Output :
For first range : 1 2 3 4 5 6 7 8 9 12 14 15 16
For second range : 15 16 18 20 21 24 25
Explanation : Largest prime factors of numbers
printed above are less than or equal to 7.
假设，我们正在检查 7-平滑数字。 1。考虑一个整数 56。这里，56 = 2 * 2 * 2 * 7。 所以，56 有两个质因数(2 和 7)，它们是< =7。所以，56 是 7-光滑数。 2。考虑另一个整数 66。这里，66 = 2 * 3 * 11。 66 有三个质因数(2、3、11)。其中 11 > 7。所以 66 不是 7-光滑数。
蛮力法:让 P 和范围[L，R]给定。这里 L < = R .创建一个循环并检查包含范围内的所有数字[L : R]。如果该数字具有最大质因数< = p，则打印该数字(即 P 平滑数字)。使用最大质因数(n) 函数计算其最大质因数/除数。
有效方法:想法是预先计算所有范围最大值的 p 光滑数。一旦我们进行了预先计算，我们就可以一个接一个地快速打印所有范围。
# Python program to display p-smooth
# number in given range.
# P-smooth numbers' array
p_smooth = [1]
def maxPrimeDivisor(n):
# Returns Maximum Prime
# Divisor of n
MPD = -1
if n == 1 :
return 1
while n % 2 == 0:
MPD = 2
n = n // 2
# math.sqrt(n) + 1
size = int(n ** 0.5) + 1
for odd in range( 3, size, 2 ):
while n % odd == 0:
# Make sure no multiples
# of prime, enters here
MPD = odd
n = n // odd
# When n is prime itself
MPD = max (n, MPD)
return MPD
def generate_p_smooth(p, MAX_LIMIT):
# generates p-smooth numbers.
global p_smooth
for i in range(2, MAX_LIMIT + 1):
if maxPrimeDivisor(i) <= p:
# Satisfies the condition
# of p-smooth number
p_smooth.append(i)
def find_p_smooth(L, R):
# finds p-smooth number in the
# given [L:R] range.
global p_smooth
if L <= p_smooth[-1]:
# If user input exceeds MAX_LIMIT
# range, no checking
for w in p_smooth :
if w > R : break
if w >= L and w <= R :
# Print P-smooth numbers
# within range : L to R.
print(w, end =" ")
print()
# p_smooth number : p = 7
# L <= R
p = 7
L, R = 1, 100
# Maximum possible value of R
MAX_LIMIT = 1000
# generate the p-smooth numbers
generate_p_smooth(p, MAX_LIMIT)
# Find an print the p-smooth numbers
find_p_smooth(L, R)
版权属于：月萌API www.moonapi.com，转载请注明出处
