Description
验证哥德巴赫猜想:任何一个大于6的偶数均可表示为两个素数之和。例如6=3+3, 8=3+5,…18=5+13(若某一偶数可分成多组素数和,只取前一个加数最小的那一个组合)。要求将6-99之间的偶数都表示成两个素数之和,输出时每行输出5组。
Input
无
Output
输出格式:每个整数占两位,且左对齐,两个式子间空格隔开。
Sample Input
Sample Output
6 =3 +3 8 =3 +5 10=3 +7 12=5 + 7 …
#include <stdio.h>
#include <stdlib.h>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
int prime(int n);
int main(int argc, char *argv[]) {
int i,j,count=0;
for(i=6;i<99;i++){
// if(i%2==0){
for(j=2;j<i;j++){
// printf("%-2d=%-2d+%-2d ",i,j,i-j);
if(prime(j)&&prime(i-j)&&i%2==0){
if(count==4){
printf("%-2d=%-2d+%-2d\n",i,j,i-j);
count=0;break;
}else{
printf("%-2d=%-2d+%-2d ",i,j,i-j);
count++;break;
}
}
}
// }
}
return 0;
}
int prime(int n){
int i;
int k;
k=1;
for(i=n-1;i>1;i--){
if(n%i==0)
k=0;
}
if(n==1)
k=0;
return k;
}
其他
C++
int findPrime(int n, int *primeNum)
{
bool *isPrime = new bool[n];
memset(isPrime, true, n*sizeof(bool));
isPrime[0] = isPrime[1] = false;
int prime = 2;
while (prime < n)
{
int mul = (prime << 1);
while (mul < n)
{
isPrime[mul] = false;
mul += prime;
}
do
{
prime++;
}
while (prime < n && !isPrime[prime]);
}
int count = 0;
for (int i = 0; i < n; i++)
{
if (isPrime[i])
{
primeNum[count] = i;
count++;
}
}
delete []isPrime;
return count;
}
int howMany(int n)
{
int *primeNum = new int[n];
int count = findPrime(n, primeNum);
int left = 0;
int right = count-1;
int result = 0;
while (left <= right)
{
int temp = primeNum[left] + primeNum[right];
if (temp == n)
{
left++;
right--;
result++;
}
else if (temp < n)
{
left++;
}
else
{
right--;
}
}
delete []primeNum;
return result;
}
int main(int argc, char *argv[])
{
cout << howMany(100);
cout << endl;
return 0;
}
JAVA
package work01;
import java.util.Scanner;
public class Day {
//判断是否是素数
/*public boolean isPrim(int n){ int i; for(i=2;i<n/2;i++){ if(n%i==0) break; } if(i>=n/2)return true; return false; }*/
//最简单的埃式筛法
public boolean isPrim(int n){
int a[]=new int [1111];
int i,j;
for(i=2;i<=n;i++){
if(a[i]==0){
for(j=i+i;j<=n;j+=i){
a[j]=1;
}
}
}
if(a[n]==0)
return true;
else
return false;
}
public void f(int n){
if(n<6||n%2==1){
return;
}
for(int i=2;i<=n-1;i++){
if(this.isPrim(i)&&this.isPrim(n-i)){
System.out.println(n+"="+i+"+"+(n-i));
}
}
}
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
System.out.print("输入一个n:");
int n=sc.nextInt();
Day g=new Day();
g.f(n);
}
}