首页 > 试题广场 >

学数学

[编程题]学数学

热度指数：1720 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

数学老师正在教授小畅和小游两人素数的概念。为了帮助巩固两人的知识，老师说出一个数，要求小游和小畅合作，每人说出一个素数，使得两人说出的素数的和刚好等于老师说出的数。请编写程序计算两人说出的素数对的个数。如，老师说10，小畅和小游可以说出两对素数，分别为（5,5）和（3,7）（不考虑顺序）。

输入描述:

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

输出描述:

输出符合条件的素数对的个数

示例1

输入

输出

算法知识视频讲解

无心2019

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

初心者托奇

a,m = int(input()),[]
for i in range(2,a):
    for j in m:
        if i % j == 0:
            break
    else:
        m.append(i)

i,j,k = 0,len(m) - 1,0
while i <= j:
    if m[i] + m[j] > a:
        j -= 1
    elif m[i] + m[j] < a:
        i += 1
    else:
        i,j,k = i + 1,j - 1,k + 1
print(k)

编辑于 2020-03-16 18:19:47 回复(0)

Java

LHC0512

Java解法

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    static ArrayList<Integer> record =new ArrayList<>();
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        recordPrimes(n);
        int count=0;
        
        //对于有序数组的双指针的方法
        int i=0;
        int j=record.size()-1;
        while (i<=j){
            int sum=record.get(i)+record.get(j);
            if (sum==n){
                count++; i++; j--;
            }
            else if (sum<n) i++;
            else j--;
        }
        System.out.println(count);
    }

    //比较快的判断是否为素数的方法
    static void recordPrimes(int n) {
        boolean[] isPrim = new boolean[n];
        Arrays.fill(isPrim, true);
        for (int i = 2; i * i < n; i++)
            if (isPrim[i])
                for (int j = i * i; j < n; j += i)
                    isPrim[j] = false;
        for (int i = 2; i < n; i++)
            if (isPrim[i]) record.add(i);
    }
}

发表于 2020-03-01 10:22:41 回复(0)

C/C++

卷积神经网络哦

这个场景打表比较合理生成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)

C/C++

nbgao

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

dragonlogin

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

C/C++

昔遥暮云

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

BetterBench

Python3实现：依次遍历1到n/2的数字i，判断i和n-i是不是素数，如果是，就计数加1。其中素数K的判断，只需要判断1到根号K的范围即可。

def isPrime(n):
    import numpy as np
    if n<=1:
        return False
    for i in range(2,int(np.sqrt(n))+1):
        if n%i ==0:
            return False
    return True 
n = input()
res = 0
for i in range(1,n//2+1):
    if isPrime(i) and isPrime(n-i):
        res+=1
print(res)

发表于 2022-08-04 11:52:31 回复(0)

C++

牛客409434554号

#include<bits/stdc++.h>
using namespace std;
inline bool check(const int &x)
{
    for(int i=2;i*i<=x;i++)
        if(x%i==0) return false;
    return true;
}
int main()
{
    int n,sum=0;cin>>n;
    int zs[1000]={0,0,1,1};
    for(int i=4;i<1000;i++)
        if(check(i))    zs[i]=1;
    for(int i=1;i<=n/2;i++)
        if(zs[i]&&zs[n-i]) sum++;
    cout<<sum<<endl;
}

发表于 2022-01-22 05:42:57 回复(0)

C/C++

牛客549207409号

#include<iostream>
#include<cmath>
bool isPrime(int i)
{
if(i==2)return true;
else
{
for(int j=2;j<=sqrt(i);j++)
{
if(i%j==0)return false;
}
}

return true;
}
int main()
{
int n;
while(std::cin>>n)
{
int count=0;
for(int i=2;i<=n/2;i++)
{
if(isPrime(i)&&isPrime(n-i))count++;
}
std::cout<<count<<std::endl;
}
return 0;
}

发表于 2020-09-17 21:37:29 回复(0)

Python

handsomefellow

def isprimer(num):
    from math import sqrt
    if num == 1:
        return False
    for i in range(2,int(sqrt(num))+1):
        if num%i == 0:
            return False
    return True

if __name__ == '__main__':
    import sys
    messages = sys.stdin.readline().strip().split()
    n = int(messages[0])
    A = []
    for ix in range(2, int(n // 2) + 1):
        iy = n-ix
        if isprimer(ix) and isprimer(iy):
            A.append(ix)
    print(len(A))

发表于 2020-05-19 10:41:00 回复(0)

hahahaaaaa

才知道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)

AI战士

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)

whathes

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)

hzdms

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)

小蝌蚪666

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

牛客372964232号

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)

lzher0

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)