题解 | #素数对#
素数对
https://www.nowcoder.com/practice/c96d6acc025541ffb79c579688f8d003
解题思路
- 题目要求找出一个正整数
的所有素数对，这些素数对的和等于
- 需要编写一个判断素数的函数
- 遍历
到
的所有数字
，判断
是否都是素数
- 如果都是素数，则找到一对素数对，计数器加1
- 最后输出计数器的值
代码
#include <iostream>
using namespace std;
bool isPrime(int n) {
if (n < 2) return false;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) return false;
}
return true;
}
int main() {
int n;
cin >> n;
int count = 0;
for (int i = 2; i <= n/2; i++) {
if (isPrime(i) && isPrime(n-i)) {
count++;
}
}
cout << count << endl;
return 0;
}
import java.util.Scanner;
public class Main {
public static boolean isPrime(int n) {
if (n < 2) return false;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) return false;
}
return true;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int count = 0;
for (int i = 2; i <= n/2; i++) {
if (isPrime(i) && isPrime(n-i)) {
count++;
}
}
System.out.println(count);
}
}
def is_prime(n):
if n < 2:
return False
i = 2
while i * i <= n:
if n % i == 0:
return False
i += 1
return True
n = int(input())
count = 0
for i in range(2, n//2 + 1):
if is_prime(i) and is_prime(n-i):
count += 1
print(count)
算法及复杂度
- 算法：暴力枚举 + 素数判定
- 时间复杂度：
- 需要遍历
的时间判断是否为素数
- 空间复杂度：
- 只需要常数级别的额外空间
