首页 > 试题广场 >

素数对

[编程题]素数对
  • 热度指数：28887 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
给定一个正整数，编写程序计算有多少对质数的和等于输入的这个正整数，并输出结果。输入值小于1000。
如，输入为10, 程序应该输出结果为2。（共有两对质数的和为10,分别为(5,5),(3,7)）

输入描述:
输入包括一个整数n,(3 ≤ n < 1000)


输出描述:
输出对数
示例1

输入

10

输出

2
算法知识视频讲解
添加回答
Java
黄小斜头像 黄小斜 
先构造素数数组，然后判断a - i 和 i 是否都为素数，是的话结果数加一。
import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int a = scanner.nextInt();
        System.out.println(couple(a));
    }
    public static int couple(int a) {
        int []arr = new int[1000];
        arr[2] = 1;
        for (int i = 3;i < a;i ++) {
            boolean flag = true;
            for (int j = 2; j < i && j <= 31; j++) {
                if (i % j == 0) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                arr[i] = 1;
            }
        }

        int res = 0;
        for (int i = 2;i <= a/2;i ++) {
            if (arr[i] == 1 && arr[a - i] == 1) {
                res ++;
            }
        }
        return res;
    }
}

发表于 2018-06-05 22:56:11 回复(0)
更多回答
pengcheng_SU头像 pengcheng_SU 
#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;	
}

编辑于 2017-08-10 17:05:41 回复(20)
Java
指offer的剑在哪？头像 指offer的剑在哪？ 

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;
	}
	
}

编辑于 2017-09-24 18:19:16 回复(10)
runK头像 runK 
#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;
}

发表于 2017-06-24 16:58:57 回复(4)
卡玛酱头像 卡玛酱 
#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;
}

发表于 2017-08-24 21:43:15 回复(2)
牛客LY头像 牛客LY 
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

发表于 2018-02-18 11:07:09 回复(0)
colining头像 colining 
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;
    }

}

编辑于 2017-07-03 18:24:29 回复(0)
深度学习ing的人头像 深度学习ing的人 

	#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;





	}

发表于 2018-06-13 23:24:09 回复(0)
一匹努力的千里马头像 一匹努力的千里马 
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;
    }
}

发表于 2018-05-11 16:05:41 回复(0)
JavaScript
Orange。头像 Orange。 
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);

发表于 2017-08-15 15:35:35 回复(0)
pein531头像 pein531
从最小的质数2开始遍历，直到n的一半（因为后一半是对称的），每次都检查拆出来的两个数是否都是质数即可。判断num是否是质数的时候从2开始检查，直到(int)sqrt(num)，看这些因子能否被num整除。 
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;
    }
}


发表于 2021-02-05 23:43:13 回复(0)
念辰六头像 念辰六 
a = int(input())
prim = []
output = 0
for i in range(2, a):
    if sum([i % j == 0 for j in range(2, int(i ** 0.5) + 1)]) == 0:
        prim.append(i)
for i in prim:
    if i <= a / 2:
        if a - i in prim:
            output += 1
    else:
        break
print(output)

发表于 2019-09-20 02:58:23 回复(0)
我要扛offer回家头像 我要扛offer回家 

	import sys





	n=int(sys.stdin.readline().strip())





	def is_prime(s):





	    if s<=1:





	        return False





	    for i in range(2,s):





	        if s%i==0:





	            return False





	    return True





	prime_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))

编辑于 2019-04-07 16:45:43 回复(0)
Python
千何头像 千何 
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里面了
编辑于 2019-03-30 02:06:31 回复(0)
cqu后起之秀头像 cqu后起之秀 
//哈哈 这方法贼** 懒得去想太多了
#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;
}

编辑于 2018-08-20 02:00:18 回复(2)
灰色与青头像 灰色与青
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList; 
public class Main {
 public static void main(String[] args) throws IOException {
  // TODO Auto-generated method stub
BufferedReader read =new BufferedReader(new InputStreamReader(System.in));
int N=Integer.parseInt(read.readLine());
prime(N);
 }
public static void prime(int N) {
 ArrayList<Integer> list=new ArrayList<>();
 int count=0;
 for(int i=3;i<N;i+=2) {
  boolean flag=true;
 cc:for(int j=3;j<=Math.sqrt(i);j+=2) {
  if(i%j==0) {
   flag=false;
  break cc;}
 }
 if(flag) {
  list.add(i);}
 }
 for(int i=0;i<list.size();i++) {
  for(int j=i;j<list.size();j++) {
   if(list.get(i)+list.get(j)==N)
    count++;
  }
 }
 System.out.print(count);
 }
}

发表于 2018-08-10 10:35:22 回复(0)
Java
不知道·就是喜欢头像 不知道·就是喜欢
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int count = 0; //存取素数对个数
        for (int i = 1; i <= num/2; i++) {
            if(fun(i) && fun(num-i)){
                count++;
            }
        }
        System.out.println(count);
    }
    private static boolean fun(int n){ //提供一个判断是否是素数的方法
        if(n <= 1){
            return false;
        }
        if(n == 2 | n== 3){
            return true;
        }
        if(n > 3){
            for (int i = 2; i <= n/2; i++) {
                if(n%i == 0){
                    return false;
                }
            }
        }
        return true;
    }
}
发表于 2018-07-26 11:16:45 回复(0)
Java
想要offer的小莫头像 想要offer的小莫
import java.util.*;

public class Demo1 {
    static int x=0;
    public static void main(String []args) {
        Scanner in=new Scanner(System.in);
        while(in.hasNext()) {
            int num=in.nextInt();
            for(int j=3;j<num;j++) {
                if(isnum(j)) {
                     if(isnum(num-j)) {
                         x++;
                         if(num-j==j) x++;
                          }
                }
            }
            System.out.println(x/2);
            }
        }
public static boolean isnum(int num) {
        for(int i=2;i<=Math.sqrt(num);i++) {
            if(num%i==0) {
                return false;
            }
        }
        return true;
    }
}

发表于 2018-04-30 13:43:53 回复(0)
Weven头像 Weven 
#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");

}
发表于 2018-04-19 15:12:12 回复(1)
Python
华科平凡头像 华科平凡 
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)
发表于 2018-04-13 15:03:57 回复(0)
Java
朕是阿朕头像 朕是阿朕 
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;
    }
}

编辑于 2018-04-09 14:17:43 回复(0)
提交观点

问题信息

C++工程师 golang工程师 2017 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 腾讯 模拟 Java工程师
难度：
216条回答 21443浏览

热门推荐

通过挑战的用户

查看代码

相关试题

素数对

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号