给定一个整数,你需要判断它是否为一个素数。 输入格式: 输入包含一个整数n。 输出格式: 如果整数是一个素数,则输出"Yes",否则输出"No"。 样例输入: 7 样例输出: Yes 样例说明: 7是一个素数。 评测用例规模与约定: 2 ≤ n ≤ 10^7。
时间: 2024-10-05 20:02:21 浏览: 24
为了判断一个整数n是否为素数,你可以采用经典的算法之一,即试除法(也称为暴力检查法)。以下是步骤:
1. 首先,从2开始,逐个检查n是否能被2到sqrt(n)之间的任何一个整数整除。这里的sqrt(n)表示n的平方根,因为如果n有因数大于它的平方根,那么必然有一个对应的小于等于平方根的因数。
2. 如果n能被其中任意一个数整除,那么n不是素数,直接输出"No"。
3. 如果n不能被这范围内的任何数整除,那么n是素数,输出"Yes"。
例如,对于样例输入7,我们可以验证7只有两个正因子1和7本身,所以它是素数。
下面是伪代码示例:
```python
def is_prime(n):
if n <= 1:
return "No"
elif n == 2 or n == 3:
return "Yes"
elif n % 2 == 0 or n % 3 == 0:
return "No"
i = 5
while i * i <= n:
if n % i == 0 or n % (i + 2) == 0:
return "No"
i += 6
return "Yes"
# 测试用例
print(is_prime(7)) # 输出 "Yes"
```
相关问题
判断一个给定的正整数是否素数 输入格式: 输入在第一行给出一个正整数N(≤ 10),随后N行,每行给出一个小于1000000 的需要判断的正整数 输出格式: 对每个需要判断的正整数,如果它是素数,则在一行中输出Yes,否则输出No
```python
def is_prime(n):
if n < 2:
return False
for i in range(2, int(n**0.5)+1):
if n % i == 0:
return False
return True
n = int(input())
for i in range(n):
num = int(input())
if is_prime(num):
print("Yes")
else:
print("No")
```
注:此题可用更优秀的算法进行优化,但此处采用最基础的算法。
用python写判断一个给定的正整数是否素数 输入格式: 输入在第一行给出一个正整数N(≤ 10),随后N行,每行给出一个小于1000000 的需要判断的正整数 输出格式: 对每个需要判断的正整数,如果它是素数,则在一行中输出Yes,否则输出No
```python
def is_prime(n):
if n <= 1:
return False
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
return False
return True
n = int(input())
for i in range(n):
num = int(input())
if is_prime(num):
print("Yes")
else:
print("No")
```
解释:
首先定义一个函数 `is_prime` 来判断一个数是否为素数,如果这个数小于等于 1,则一定不是素数,直接返回 `False`。否则,从 2 开始到该数的平方根(向上取整)的范围内,看是否有数能整除它,有则返回 `False`,否则返回 `True`。
接下来读入数据,对于每个需要判断的数,调用 `is_prime` 函数来判断是否为素数,是则输出 "Yes",否则输出 "No"。