当前位置:网站首页>7-15 h0161. Find the greatest common divisor and the least common multiple (PTA program design)
7-15 h0161. Find the greatest common divisor and the least common multiple (PTA program design)
2022-07-06 13:56:00 【Programming Lindaiyu】
Enter two positive integers a and b, Find the greatest common divisor and the least common multiple .
Input format :
Enter... On one line 2 No more than one. 100000 The positive integer A and B.
Output format :
stay 2 Output in line A、B The greatest common divisor and the least common multiple of .
sample input :
42 36
sample output :
The greatest common divisor is :6
The least common multiple is :252
Code (Python):
Method 1 ( Easier to understand ):
a,b=map(int,input().split()) # Input of two numbers
d=max(a,b) # use Python The built-in function finds the larger of the two numbers
x=min(a,b) ## use Python The built-in function finds the smaller of the two numbers
# Find the greatest common divisor
for i in range(x,0,-1): # Because the greatest common divisor must be smaller than both numbers , And find the maximum value in the common divisor , So start with a smaller number and try until 0( barring 0), Because it's trying backwards , So the step size is set to -1
if a%i==0 and b%i==0: # If you encounter a number that can be divided by two numbers at the same time , Then it must be the greatest common divisor , be break Exit loop
print(" The greatest common divisor is :%d"%i) # Output... In format
break # Exit loop
# Find the least common multiple
for i in range(d,a*b+1): # Because the least common multiple must be greater than both numbers , And find the minimum value of the common multiple , So try from the larger number to a*b, because a*b It must be their common multiple , And the least common multiple must be less than or equal to a*b
if i%a==0 and i%b==0: # If you encounter a number that can divide two numbers at the same time , Then it must be the least common multiple
print(" The least common multiple is :%d"%i) # Output... In format
break # Exit loop
Method 2 :
a,b=map(int,input().split()) # Note that this can't be a=int(input()) b=int(input()) because input Will read all strings in a row
m=a # The first a,b The value of , In case the following will a,b After changing the value of a,b The real value is lost
n=b
res=m%n # To find the greatest common divisor, first divide the two numbers and take the remainder
while(res!=0): # Determine whether the remainder is 0, if 0 Then the divisor is the greatest common divisor
a=b # If not 0, Then assign the value of the divisor to the dividend , Assign the remainder to the divisor
b=res
res=a%b # Continue to divide , Ready for the next cycle
x1=b # Used to store the value of the final divisor , The greatest common divisor
x2=m*n/x1 # According to a mathematical formula , That is, the least common multiple is the product of two numbers and then divided by the greatest common divisor
print(" The greatest common divisor is :%d"%x1) # Output... In format
print(" The least common multiple is :%d"%x2)
Here are two ways to find the greatest common divisor and the least common multiple , You can choose different methods according to your own situation , Encourage everyone to master both methods !
The above program gives more detailed comments , For novice Xiaobai's reference . The idea of program design or code implementation is not optimal , You are welcome to correct your mistakes or give better ideas .
I am a rookie who wants to be Kunpeng , Everyone's encouragement is my driving force , Welcome to like collection comments !
边栏推荐
- HackMyvm靶机系列(5)-warez
- Using spacedesk to realize any device in the LAN as a computer expansion screen
- 实验五 类和对象
- . Net6: develop modern 3D industrial software based on WPF (2)
- MATLAB打开.m文件乱码解决办法
- Redis的两种持久化机制RDB和AOF的原理和优缺点
- The difference between abstract classes and interfaces
- 【VMware异常问题】问题分析&解决办法
- Attach the simplified sample database to the SQLSERVER database instance
- 【Numpy和Pytorch的数据处理】
猜你喜欢
This time, thoroughly understand the MySQL index
Read only error handling
[面試時]——我如何講清楚TCP實現可靠傳輸的機制
【VMware异常问题】问题分析&解决办法
Canvas foundation 1 - draw a straight line (easy to understand)
Leetcode.3 无重复字符的最长子串——超过100%的解法
Principles, advantages and disadvantages of two persistence mechanisms RDB and AOF of redis
编写程序,模拟现实生活中的交通信号灯。
QT meta object qmetaobject indexofslot and other functions to obtain class methods attention
MySQL事务及实现原理全面总结,再也不用担心面试
随机推荐
一段用蜂鸣器编的音乐(成都)
MySQL锁总结(全面简洁 + 图文详解)
[MySQL database learning]
透彻理解LRU算法——详解力扣146题及Redis中LRU缓存淘汰
[MySQL table structure and integrity constraint modification (Alter)]
Thoroughly understand LRU algorithm - explain 146 questions in detail and eliminate LRU cache in redis
SRC mining ideas and methods
这次,彻底搞清楚MySQL索引
【数据库 三大范式】一看就懂
优先队列PriorityQueue (大根堆/小根堆/TopK问题)
[au cours de l'entrevue] - Comment expliquer le mécanisme de transmission fiable de TCP
Simply understand the promise of ES6
7-9 制作门牌号3.0(PTA程序设计)
[the Nine Yang Manual] 2022 Fudan University Applied Statistics real problem + analysis
QT meta object qmetaobject indexofslot and other functions to obtain class methods attention
HackMyvm靶机系列(5)-warez
.Xmind文件如何上传金山文档共享在线编辑?
2022 Teddy cup data mining challenge question C idea and post game summary
Cookie和Session的区别
MySQL中count(*)的实现方式