首页 > 试题广场 > 学数学
[编程题]学数学
  • 热度指数:750 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
数学老师正在教授小畅和小游两人素数的概念。为了帮助巩固两人的知识,老师说出一个数,要求小游和小畅合作,每人说出一个素数,使得两人说出的素数的和刚好等于老师说出的数。请编写程序计算两人说出的素数对的个数。如,老师说10,小畅和小游可以说出两对素数,分别为(5,5)和(3,7)(不考虑顺序)。

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


输出描述:
输出符合条件的素数对的个数
示例1

输入

10

输出

2
#include<bits/stdc++.h>
using namespace std;
int sushu(int n)
{
    int i=2,res=1;
    for(;i<n;i++)
    {
        if(n%i==0)
        {
            res=0;
            break;
        }
    }
    return res;
}
int main()
{
    int n,res=0;
    cin>>n;
    for(int i=2;i<=n/2;i++)
    {
        if(sushu(i)&&sushu(n-i))
            res++;
    }
    cout<<res<<endl;
    return 0;
}

发表于 2019-08-19 22:28:21 回复(0)
这个场景打表比较合理 生成n以内的所有质数表 这样可以在O(1)时间内判断是否为质数
#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e3 + 5;
int vis[maxn];

void eratosThenes(int n) { //n以内所有素数表
	memset(vis, 0, sizeof(vis));
	int m = sqrt(n + 0.5);
    vis[1] = 1;  // 1不是质数
	for(int i = 2; i <= m; i++) {  //时间复杂度O(nlogn)
		if(!vis[i]) {
			for(int j = i * i; j <= n; j += i) 
				vis[j] = 1;  //vis=1表示不是素数
		}
	}	
}

int main(){
    int n, res = 0; cin >> n;
    eratosThenes(n);
    for(int i = 1; i <= n - i; i++) {
        if(!vis[i] && !vis[n-i]) res++;
    }
    cout<<res<<endl;
}


发表于 2019-12-12 11:54:45 回复(0)
#include <iostream>
using namespace std;
bool isshu(int n);
int main()
{
    int n;
    cin >> n;
    int cnt = 0;
    for(int i = 2;i<=n/2;i++)
    {
        if(isshu(i)&&isshu(n-i))
            cnt++;
    }
    cout << cnt << endl;
    return 0;
}
bool isshu(int n)
{
    for(int i = 2;i<=n/2;i++)
    {
        if(n%i==0)
            return 0;
    }
    return 1;
}

发表于 2019-11-23 11:22:34 回复(0)
#include <bits/stdc++.h>
using namespace std;

bool isPrime(int x){
    if(x==1)
        return false;
    else if(x==2)
        return true;
    for(int i=2;i<=sqrt(x);i++)
        if(x%i==0)
            return false;
    return true;
}

int main(){
    int n, cnt=0;
    bool a[1001];
    for(int i=1;i<=1000;i++)
        a[i] = isPrime(i);
    cin>>n;
    for(int i=2;i<=n/2;i++)
        if(a[i] && a[n-i])
            cnt++;
    cout<<cnt<<endl;
    return 0;
}

发表于 2019-10-29 02:43:30 回复(0)
#include<bits/stdc++.h>
using namespace std;
#define N 1005
bool f[N];
// 素数打表
void db() {
	// false == susu
	// true != susu
	for (int i=2; i<=N; ++i) {
		if (!f[i]) {
			for (int j=i*i; j<=N; j+=i) {
				f[j] = true;
			}
		}
	}
}
int main() {
	int n;
	cin >> n;
	int ans = 0;
    int r = n;
    db();
	for (int i=3; i<r; ++i) {
		if (!f[i] && !f[n-i]) {
			++ans;
            r = n - i; // 去重
		} 
	}
	cout << ans << endl;
	return 0;
}

发表于 2019-10-22 20:57:38 回复(0)
#include <bits/stdc++.h>
using namespace std;
//筛选法求素数
void solve(vector<bool> &vis,int n)
{
    for(int i=2;i<n;i++)
    {
        int j=2;
        double k=sqrt(i);
        while(j<=k){
            if(i%j==0)
                break;
            j++;
        }
        if(j>k)
            vis[i]=true;
    }
}
int main(){
    int n,sum=0;
    cin>>n;
    vector<bool> vis(n,false);
    solve(vis,n);
    for(int i=2;i<=n>>1;i++)    //到n/2停止,去重
        if(vis[i]&&vis[n-i]){   //同时为素数
            sum++;
        }
    cout<<sum;
    return 0;
}

发表于 2019-09-09 14:26:00 回复(0)
才知道1居然不是素数。。。
import java.util.*;
public class Main{
    public static void main(String[] args){
        int[] a=new int[1000];
        int count=0;
        Scanner sc=new Scanner(System.in);
        int num=sc.nextInt();
        int m=(int)Math.sqrt(num+0.5);
        for(int i=2;i<=m;i++){
            if(a[i]!=1)for(int j=i*i;j<=num;j+=i){
                a[j]=1;
            }
        }
        for(int i=2;i<num-1;i++){
            if(a[num-i]==0&&a[i]==0){
                count++;
            }
            a[i]=2;
        }
        System.out.println(count+"");
    }
}


发表于 2019-11-19 14:48:38 回复(0)
def isPrime(n):
    if n <= 3:
        return n > 1
    if n % 6 != 1 and n % 6 != 5:
        return False
    sqrt = int(n ** 0.5)
    for i in range(5, sqrt + 1, 6):
        if n % i == 0 or n % (i + 2) == 0:
            return False
    return True

def get_priTuple(n):
    data = [i for i in range(n + 1) if isPrime(i)]
    count = 0
    for i in range(len(data)):
        if n - data[i] in data[i+1:]:
            count += 1
    if n / 2 in data: count += 1
    return count

n = int(input())
print(get_priTuple(n))

https://blog.csdn.net/afei__/article/details/80638460  判断素数
发表于 2019-10-16 15:55:39 回复(0)
import sys

def IsPrime(n):
    for i in range(2,int(pow(n,0.5))+1):
        if n%i==0:
            return False
    return True

def decomposition(n):
    count = 0
    for i in range(2,n//2+1):
        if IsPrime(i) and IsPrime(n-i):
            count+=1
    return count

if __name__ == "__main__":
    n = int(input().strip())
    print(decomposition(n))
发表于 2019-09-27 20:27:33 回复(0)
import java.util.*;
public class Main{
    
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n =sc.nextInt();
        int left=0;
        int right=0;
        int count=0;
        List<Integer> Sus=new ArrayList<>();
        Sus.add(2);
        if(n<3){
        	System.out.println(0);
        	return;
        }
        for(int i=3;i<n;i++){
            for(int j=2;j<=i;j++){
                if(j==i){
                    Sus.add(i);
                }
                if(i%j==0){
                    break;
                }
            }
        }
        right=Sus.size()-1;
        while(left<=right){
            if(Sus.get(left)+Sus.get(right)<n){
                left++;
                continue;
            }
            if(Sus.get(left)+Sus.get(right)>n){
                right--;
                continue;
            }
            if(Sus.get(left)+Sus.get(right)==n){
                count++;
                left++;
            }
        }
        System.out.println(count);
        
        
    }
    
}
我的是最笨的方法
发表于 2019-09-08 18:38:58 回复(0)
n = int(input())

primes = set([2])
for i in range(3, n + 1):
    is_prime = True
    for prime in primes:
        if i % prime == 0:
            is_prime = False
            break
    if is_prime:
        primes.add(i)

cnt = 0
for prime in primes:
    if prime <= n // 2 and n - prime in primes:
        cnt += 1
print(cnt)

发表于 2019-09-03 18:24:11 回复(0)
#include <iostream>
#include <set>
#include <cmath>
using namespace std;
bool isprime(int x){
    for(int j = 2; j <= sqrt(x); ++j){
        if(x % j ==0)
            return false;
    }
    return true;
}
int main(void){
    int n, count = 0;
    set<int> prime;
    cin>>n;
    for(int i = 2; i <= 1000; ++i){
        if(isprime(i))
            prime.insert(i);
    }
    for(auto x : prime){
        if(x*2 > n)
            break;
        else if(prime.count(n-x))
            ++count;
    }
    cout<<count<<endl;
    return 0;
}
把2到1000的素数保存在集合中,然后遍历集合元素,因为集合是已经排好序的,当遍历元素x*2>n时停止搜索,然后判断n-x是否也在素数集合中
发表于 2019-08-23 10:11:27 回复(0)
C++忘了在哪看的了
//依次找2-n的整数倍记录
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    int res = 0;
    int n; cin >> n;
    vector<bool> vec(n+1,false);
    //将n中所有的素数计算出来
    for(int i = 2; i < sqrt(n);i++)
    {
        if(!vec[i])
        {
            for(int j = 2; j * i <= n;j++)
            {
                vec[i*j] = true;
            }
        }
    }
    int left = 2;
    int right = n - 1;
    while(left <= right)
    {
        while(left <= right && vec[left]) left++;
        while(left <= right && vec[right]) right--;
        if(left <= right)
        {
            if(left + right == n) 
            {
                left++;right--;
                 res++;   
            }
            else if(left + right > n){
                right--;
            }
            else left++;
        }
    }
    cout << res << endl;
    return 0;
}


发表于 2019-08-13 20:56:26 回复(0)
def isprime(n):
    for i in range(2, n):
        if n%i == 0:
            return False
    return True

n = int(input())
res = 0
for i in range(2,n//2+1):
    if isprime(i):
        if isprime(n-i):
            res += 1
print(res)

发表于 2019-08-01 22:11:36 回复(0)