输入包括一个整数n,(3 ≤ n < 1000)
输出符合条件的素数对的个数
10
2
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); } }
#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; }
#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; }
#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; }
#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; }
#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; }
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)
#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; }
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+""); } }
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))
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); } }我的是最笨的方法
#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是否也在素数集合中
//依次找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; }