给定一个正整数,编写程序计算有多少对质数的和等于输入的这个正整数,并输出结果。输入值小于1000。
如,输入为10, 程序应该输出结果为2。(共有两对质数的和为10,分别为(5,5),(3,7))
#include <iostream> #include <vector> using namespace std; int main(){ //筛选法求素数(删除所有素数的倍数) vector<int> v(1000,1); for(int i=2;i<1000;++i){ for(int j=2;i*j<1000;++j){ if(v[i]){ v[i*j]=0; } } } int x; cin>>x; int res=0; for(int i=2;i<=x/2;++i){ if(v[i]&&v[x-i]) ++res; } cout<<res<<endl; }
import java.util.Scanner; public class StringUtil { //素数对 public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int sum = 0; for(int i=2; i<=n/2; i++){ if(isss(i) && isss(n-i)){ sum++; } } System.out.println(sum); } //判断是否为素数 public static boolean isss(int n){ for(int i=2; i<=Math.sqrt(n); i++){ if(n%i == 0) return false; } return true; } }
#include<iostream> #include<vector> #include<cmath> //判断是否为素数 bool isPrime(int n) { //注意是<=..... for (int i = 2; i <= sqrt(n); i++) if (n % i == 0) return false; return true; } //保存1000以内的素数 void PrimeIn1000(vector<int> &vec) { vec.push_back(2); for (int i = 3; i < 1000; i++) if (isPrime(i)) vec.push_back(i); } //用两个迭代器分别指向vector的头尾,遇大则尾退,遇小则头进 int SumofPrimePair(int n) { vector<int> PrimeVec; PrimeIn1000(PrimeVec); int result = 0; vector<int>::iterator iterLeft = PrimeVec.begin(); vector<int>::iterator iterRight = PrimeVec.end()-1; while (iterLeft <= iterRight) { int tempSum = *iterLeft + *iterRight; if (tempSum == n) { result++; iterLeft++; iterRight--; } else if (tempSum < n) iterLeft++; else iterRight--; } return result; } int main() { int n; cin >> n; cout << SumofPrimePair(n) << endl; system("pause"); return 0; }
#include <iostream> #include <cmath> using namespace std; bool isPrime(int n){ if(n==1) return false; for(int i=2;i<=sqrt(n);i++){ if(n%i==0){ return false; } } return true; } int main(){ int i,n,cnt=0; cin>>n; for(i=2;i<=(n+1)/2;i++){ if(isPrime(i)&&isPrime(n-i)){ cnt++; } } cout<<cnt<<endl; }
n = int(raw_input()) arr,res = [], 0 for i in range(2, n + 1): flag = True for j in range(2, int(i**0.5) + 1): if i % j == 0: flag = False break if flag: arr.append(i) for i in range(len(arr)): if arr[i] > n / 2: break else: if n - arr[i] in arr: res += 1 print res
public class FindPrimePair { /** * 给定一个正整数,编写程序计算有多少对质数的和等于输入的这个正整数,并输出结果。输入值小于1000。 * 如,输入为10, 程序应该输出结果为2。(共有两对质数的和为10,分别为(5,5),(3,7)) * @param args */ public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int i = scanner.nextInt(); System.out.println(findPrimePair1(i)); } /** * 方法一:先把素数都求出来,然后头尾指针寻找正确的值<br> * * @param sum * @return */ private static int findPrimePair(int sum) { if (sum <= 3) { return 0; } ArrayList<Integer> arrayList = new ArrayList<>(); int num = 0; for (int i = 2; i < 1000; i++) { if (isPrime(i)) { arrayList.add(i); } } int minIndex = 0; int maxIndex = arrayList.size() - 1; while (minIndex <= maxIndex) { if (arrayList.get(minIndex) + arrayList.get(maxIndex) > sum) { maxIndex--; } else if (arrayList.get(minIndex) + arrayList.get(maxIndex) < sum) { minIndex++; }else { num ++; minIndex++; } } return num; } /** * 方法二:通过sum,确定质数存在范围;<br> * 然后遍找质数边做,时间复杂度提高,空间复杂度降低; * @param sum * @return */ private static int findPrimePair1(int sum) { if (sum <= 3) { return 0; } int count=0; for (int i = 2;i<=sum/2;i++) { for (int j = 2 ; j <sum-i+1;j++) { if (isPrime(i) && isPrime(j)&& (i+j)==sum) { count++; } } } return count; } private static boolean isPrime(int i) { for (double j = 2; j <= Math.sqrt(i); j++) { if (i % j == 0) { return false; } } return true; } }
#include<iostream>#include<cmath>using namespace std;bool isPrime(int num);int main(){int n;cin>>n;int sum = 0;for(int i=2; i<=n/2; ++i){if(isPrime(i)&&isPrime(n-i))sum += 1;}cout<<sum;return 0;}bool isPrime(int num){for(int i=2; i<=(int)sqrt(num); ++i)if(num%i == 0)return false;return true;}
import java.util.*; public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int res = 0; for(int i = 2; i <= n/2 ;i++) { if(isDigit(i) && isDigit(n-i)) res++; } System.out.println(res); } //是否为素数 private static boolean isDigit(int m) { int i = 2; while(m%i != 0) { i++; } if(i == m) return true; return false; } }
var n = parseInt(readline()); //len以内的所有素数 function prime(len){ var arr = [2]; for(var i = 3; i < len; i+=2){ for(var j=2; j < i; j++){ if(i%j === 0) { break; } } if(i <= j && i !=1){ arr.push(i); } } return arr; } var newArr = prime(n); var cnt = 0; for(var i=0; i<newArr.length; i++){ for(var j=newArr.length-1; j>=0; j--){ if(i<=j && newArr[i]+newArr[j] == n){ cnt++; } } } console.log(cnt);
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine().trim()); int count = 0; for(int num = 2; num <= n / 2; num++) if(isPrime(num) && isPrime(n - num)) count++; System.out.println(count); } private static boolean isPrime(int num) { for(int factor = 2; factor <= (int)Math.sqrt(num); factor++) if(num % factor == 0) return false; // 有除了1之外的因子,不是质数 return true; } }
import sysn=int(sys.stdin.readline().strip())def is_prime(s):if s<=1:return Falsefor i in range(2,s):if s%i==0:return Falsereturn Trueprime_list=list(filter(lambda c:is_prime(c),range(2,n)))res=[]for i in prime_list:for j in prime_list:if i+j==n and (j,i) not in res:res.append((i,j))print(len(res))
n = int(input()) primes = [2, ] for i in range(3, n): active = True for j in range(2, i): if i % j == 0: active = False break else: continue if active: primes.append(i) pair = 0 for x in primes: if n-x in primes: pair += 1 pair = int(pair/2+0.5) print(pair)菜鸟参考了一下评论大神的代码改的,因为不太会处理数字1,2的j循环部分,干脆把2直接放到初始primes里面了
//哈哈 这方法贼** 懒得去想太多了 #include<iostream> #include<vector> using namespace std; bool isp(int n){//判断质数 int count=0; for(int i=2;i<n;i++){ if(n%i==0){count++;} } return count==0; } int main(){ int size=0,n,cnt=0,index=0; vector<int>a(1000); for(int i=2;i<1000;i++){ if(isp(i)){ a[index++]=i;//把1000内的质数都存vector<int>a里 size++;//质数个数 } } cin>>n; for(int i=0;i<size;i++){//嵌套for循环让所有的a中元素交叉相加 for(int j=0;j<size;j++){ if(a[i]+a[j]==n){//过滤出符合要求的 cnt++; if(a[i]==a[j]){//这里要考虑相等情况,此时没有重复 cnt++; } } } } cout<<cnt/2<<endl; return 0; }
public class Main {
#include <iostream> using namespace std; bool prime_num(int n) { for (int i = 2; i <= n - 1; i++) { if (n%i == 0) { return false; } } return true; } int main() { int n; int result = 0; cin >> n; //先判断当前循环i值是不是质数,再判断n-i是不是质数 for (int i = 2; i < n / 2 + 1; i++) { if (prime_num(i) == true && prime_num(n - i) == true) { result++; } } cout << result << endl; system("pause"); }
from math import sqrt
def isPrimeNumber(number):
for i in range(2, int(sqrt(number) + 1)):
if number % i == 0:
return False
return True
def getPrimeNumber(number):
res = []
for i in range(2, number + 1):
if isPrimeNumber(i):
res.append(i)
return res
a = int(input())
res = 0
primes = getPrimeNumber(a)
for i in primes:
if a - i in primes and i < a // 2 + 1:
res += 1
print(res)
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int n = in.nextInt();
List<Integer> li = zhishu(n);
int count=0;
/*
思路:在n以内的质数集合li中(集合已经是有序的)定义一个头指针i和一个尾指针j
从两边遍历,如果找到一对这样的数,计数器自增,继续循环找;如果找到的数
之和比n小,说明此次循环没必要继续找下去了(因为越往下找越小),所以直接
break内循环;如果找到的数之和比n大,说明尾指针需要往左移(往左数越小)
那么直接继续内循环就行。
*/
for(int i=0;i<=li.size();i++){
for(int j=li.size()-1;j>=i;j--){
if(li.get(i)+li.get(j)==n){
count++;
}else if (li.get(i)+li.get(j)<n){
break;
}else {
continue;
}
}
}
System.out.println(count);
}
//输入正整数n;输出n以内所有的质数集合
public static List<Integer> zhishu(int n){
boolean flag ;
List<Integer> li = new ArrayList();
for(int i=2;i<=n;i++){
flag =true;
for(int j=2;j<=(int)Math.sqrt(i);j++){
if(i%j==0)
flag = false;
}
if(flag){
li.add(i);
}
}
return li;
}
}