Home >> Python >> Algorithms

■制御構文を用いたアルゴリズムの記述例

	
	# 素数を求める（簡易版）
	
	limit = input( "Input limit number")
	for n in range(1, limit):
		isPrime = True
		for d in range( 2, n ):
			if n % d == 0:
				isPrime = False
				break
		if isPrime:
			print( n, end=" " )
	print( )
	

	
	# 素数を求める
	# エラトステネスの篩（ふるい）
	# それまで求めた素数のリストを用いる

	limit = input( "Input limit number")
	primes = [ ]
	for n in range(2, limit):
		isPrime = True
		for d in primes:
			if n%d== 0:
				isPrime = False
				break
				
		if isPrime:
			primes +=[ n ]
	#		print n,
	print( primes )
	

	
	# 最大公約数（greatest common divisor）
	# 最小公倍数（least common multiply）
	# ユークリッドの互除法を使って（Euclidean algorithm）
	
	x = input( "Input Number")
	y = input( "Input Another Number")
	
	w = max(x, y)
	u = min(x, y)
	while w % u != 0:
		w, u = u, w % u
	
	print( "GCD of " + str(x)+ " and "+str(y)+" is "+ str(u))
	print( "LCM of " + str(x)+ " and "+str(y)+" is "+ str(x//u*y//u*u))
	

	
	# 素因数分解
	# factorize into a mulitply of prime numbers
	# 素数が3以上は奇数であり、その差分が、2, 4の倍数であることを利用して
	
	x = input( "Input Number")
	table = [ 1, 2, 2, 4]
	print(  str(x)+" to be decomposed to ", end ="  " )
	d = 2
	i = 0
	n = x
	prime = []
	while n > d:
		if n % d == 0:
			n = n // d
			prime = prime + [ d ]
		else:
			d = d + table[ i ]
			if i >= 3:
				i = i - 1
			else:
				i = i + 1
	prime = prime + [ n ]
	print( prime )