查找组成一个偶数最接近的两个素数_

C

小峰-sinx

#include <stdio.h>

int is_sushu(int n) {

for (int i = 2; i <= n / 2; ++i) {

if (n % i == 0) {

return 0;

}

return 1;

}

int main() {

int a;

int flag = 0;

scanf("%d", &a);

for (int i = a / 2; i >= 2; i--) {

if (is_sushu(i) && is_sushu(a - i)) {

printf("%d\n%d", i, a - i);

break;

}

return 0;

}

发表于 2024-08-21 17:51:16 回复(0)

C

唐凌Zero

#include <stdio.h>

// 提前生成小于1000的质数表，可减少时间复杂度
#define list_size   168

int prime_list[list_size]={2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997};

int main()
{
    int x;
    scanf("%d",&x);
    int a=0,b=1000;
    for(int i=0;i<list_size;i++)
    {
        for(int j=i;j<list_size;j++)
        {
            int aa=prime_list[i];
            int bb=prime_list[j];
            if(aa+bb==x)
            {
                if(bb-aa<b-a)
                {
                    b=bb;
                    a=aa;
                }
            }
        }
    }
    printf("%d\n%d",a,b);
    return 0;
}

发表于 2024-08-13 20:19:03 回复(0)

C

VictorGao

#include <stdio.h>
#include<math.h>
int zhishu(int x)
{
    int i;
    for(i=2;i<=sqrt(x);i++)
    {
        if(x%i==0)
        return 0;
    }
    return 1;
}

int main() {
    int a, i,j,flag,cha,i1,j1;
    scanf("%d",&a);
    cha=a;
    for(i=2;i<=a/2;i++)
    {
        for(j=2;j<a;j++)
        {
            if(zhishu(i) && zhishu(j) && (i+j)==a)
            {
                if(cha>(j-i))
                {
                    i1=i;
                    j1=j;
                    cha=j-i;
                }
            }
            
        }
    
    }
    printf("%d\n%d",i1,j1);

    return 0;
}

编辑于 2024-03-06 19:29:45 回复(0)

C

墨夜风名

#include <stdio.h>

int isStone(int value)
{
    for(int i=2;i<value;i++){
        if(value % i == 0){
            return -1;
        }
    }
    return 0;
}

int findStone(int *arr,int len, int value)
{
    for(int i=0;i<len;i++){
        if(value == arr[i]){
            return 0;
        }
    }
    return 1;
}

int main() {
    int n;
    int arr[1000];
    int len = 0;
    
    scanf("%d", &n);

    for(int i=2;i<n;i++){
        if(isStone(i) == 0){
            arr[len++] = i;
        }
    }

    int minA =0;
    int minB =0;
    unsigned int min = -1;

    for(int i=0;i<len;i++){
        int a = arr[i];
        int b = n - arr[i];

        if(findStone(arr, len, b) != 0){
            continue;
        }
        
        int temp = a > b?a-b:b-a;
        if(temp < min){
            minA = a;
            minB = b;
            min = temp;
        }
    }
    printf("%d\n", minA);
    printf("%d\n", minB);

    return 0;
}

编辑于 2024-03-01 10:35:02 回复(0)

C

牛客770548236号

#include <math.h>

#include <stdio.h>

//判断是不是素数

int isprime(int n)

{

if(n == 2)

return 1;

else if(n%2==0)

return 0;

else

{

for(int i=2; i*i<=n; i++)

{

if(n%i==0)

return 0;

}

return 1;

}

void math(int n)

{

int i =2;

int min =n;

for(i=2;i<=(n/2);i++)

{

if(isprime(i)&&isprime(n-i))//判断两个数是不是都是素数

{

if(min>((n-i)-i))//计算差值

min =(n-i)-i;

}

printf("%d\n%d",(n-min)/2,n-((n-min)/2) );//根据差值最小还原素数

}

int main()

{

int n = 0;

scanf("%d",&n);

math(n);

return 0;

}

发表于 2023-12-10 17:12:08 回复(0)

C

猪猪侠的飞天梦

#include <math.h>
#include <stdio.h>
# include "math.h"
int main() {
    int n, b[500] = {0}, j = 0; 
    scanf("%d",&n);
    for(int i = 1; i<n; i += 2){
        int bi = 1;
        for(int k = 2; k<=i/2; k++){
            if(i%k==0) bi = 0;
        }
        if(bi) b[j++] = i;
    }
    b[0] = 2;
    //printf("%d\n",j);                               //b中包含k个1000以内的素数
    int mi = 1000, max = 0, min = 1000;
    for(int i=0; i<j; i++){
        for(int k = i; k<j; k ++){
            if(b[i] + b[k]  == n){
                if(b[j]-b[k]<mi){
                    mi = b[k]-b[i];
                    max = b[k];
                    min = b[i];
                }
            }
        }
    }
    printf("%d\n%d",min,max);
    return 0;
}

发表于 2023-12-03 17:47:11 回复(0)

C

彭洋a

#include <stdio.h>

int isprime(int n)

{

for(int i = 2;i*i<=n;i++)

{

if(n%i == 0)

{

return 0;

}

return 1;

}

int main() {

int a;

while (scanf("%d", &a) != EOF) {

int b = a/2;

for(int i = 0;i<b;i++)

{

if(isprime(b-i)&&isprime(b+i))

{

printf("%d\n%d\n",b-i,b+i);

break;

}

return 0;

}

发表于 2023-10-11 21:24:14 回复(0)

C

goForWork

#include <stdio.h>

int main() {

//无疑问两个素数必定是一个大于等于n/2,和小于等于n/2的素数

int isSS(int m);

int n;

scanf("%d",&n);

int miner=n/2,maxer=n/2;

while (!isSS(maxer)) maxer++;

while (!isSS(miner)) miner--;

while (1) {

if (n==maxer+miner) {

printf("%d\n%d",miner,maxer);

break;

}else if (n>maxer+miner) {

maxer++;

while (!isSS(maxer)) maxer++;

}else {

miner--;

while (!isSS(miner)) miner--;

}

int isSS(int m){

for (int i=2; i<m; i++) {

if (m%i==0) {

return 0;//不是素数

}

return 1;//是素数

}

发表于 2023-08-29 21:30:51 回复(0)

C

烦恼的火龙果

#include <math.h>
#include <stdio.h>

int sushu[1000]={0},top=0,s_min,s_max;

void compute_sushu(int num){
    for(int i=2;i<num;i++){
        int flag=0;
        for(int k=2;k<i;k++){
            if(i%k==0){
                flag=1;
                break;
            }
        }
        if(flag==0){
            sushu[top]=i;
            top++;
        }
    }
}
void comp(int num){
    int min=1000;
    for(int i=0;i<top;i++){
        for(int k=i;k<top;k++){
            if((sushu[i]+sushu[k])==num){
                if(min>(sushu[k]-sushu[i])){
                    min=sushu[k]-sushu[i];
                    s_max=k;
                    s_min=i;
                }
            }
        }
    }
}

int main() {
    int num;
    
    scanf("%d",&num);
    compute_sushu(num);//计算得出一个素数表
    comp(num);//计算得到两个差值最小的素数在素数表的下标
    printf("%d\n%d",sushu[s_min],sushu[s_max]);
    return 0;
}

发表于 2023-04-16 17:00:31 回复(0)

C

Lee QL

#include <stdio.h>
#include <math.h>

int zhishu(int num) {
    int i;
    if (num < 2) {                  //小于2非质数
        return  0;
    }
    for (i = 2; i <= sqrt(num); i++) {
        if (num % i == 0) {        //可被整除非质数
            return 0;
        }
    }
    return 1;                     //其余质数
}


int main() {
    int l, m, num, i;
    scanf("%d", &num);
    l = m = num / 2;
    for (i = 0; l - i >= 2; i++) {
        if (zhishu(l - i) && zhishu(m + i)) {
            printf("%d\n%d", l - i, m + i);
            break;
        }
    }
    return 0;
}

发表于 2023-04-12 19:58:47 回复(0)

C

忘忧萱

#include <stdio.h>

int main() {
    /**显然对于一个偶数来说，差值最小的素数对应该最靠近其中轴的数字n/2
    因此只需要从其中轴开始向上或者向下遍历，同时保证找到的两个数都是素数
    那么就找到了题目要求的素数对*/
    int n;
    scanf("%d",&n);
    //if (n == 4) printf("2\n2\n");
    for (int i = n / 2; i <= n; i++) {
        int maybe = i;
        int flag = 0;
        for (int j = 2; j * j <= maybe; j++) {
            if (maybe % j == 0) {
                flag = 1;
                break;
            }
        }
        if (flag == 0) {
            int flag2 = 0;
            for (int j = 2; j * j <= (n-maybe); j++) {
                if ((n-maybe) % j == 0) {
                    flag2 = 1;
                    break;
                }
            }
            if(flag2==0) {
                printf("%d\n%d\n",n-maybe,maybe);
                break;
            }
        }
    }
    return 0;
}

如上，从中轴开始遍历，最先找到的就是满足条件的。

发表于 2023-01-01 16:31:23 回复(1)

C

Hongky

#include <stdio.h>
#include <math.h>

int main()
{
int n;
int a,b;
scanf("%d",&n);
int A=n-2,B=2;
int i;
for(int j=2;j<=n/2;j++){
for(i=2;i<=sqrt(j);i++) //查找素数a
if(j%i==0)
break;
if(i>sqrt(j))
a=j; //找到a
else
continue;

for(i=2;i<=sqrt(n-a);i++) //查找素数b
if((n-a)%i==0)
break;
if(i>sqrt(n-a))
b=n-a; //找到b
else
continue;

if(abs(a-b)<abs(A-B))
A=a;B=b;
}
printf("%d\n%d",A,B);

return 0;
}

发表于 2022-07-19 23:15:26 回复(0)

C

好久不见，最近好吗

//基本思路：

//取数中值,左右同步移动，判断两者同为素数就好

/*

20

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

i<--- || --->j

*/

#include <stdio.h>

#include <stdlib.h>

int is_primer(int n)
{
int i = 0,flag = 0;
for(i = 2; i < n; i++)
{
if(n%i == 0)
{
return 0;
}
}
return 1;
}

int main(void)
{
int n;
scanf("%d",&n);

int i = 0,j = 0;
for(i = n/2,j = n/2; i>1,j<n; i--,j++)
{
if(is_primer(i) && is_primer(j))
{
printf("%d\n",i);
printf("%d\n",j);
break;
}
}
return 0;
}

发表于 2022-06-18 12:15:24 回复(0)

C

发家致富奔小康

#include <stdio.h>
int flag(int n)
{
int i,flag;
if(n==1)
{
flag=0;

}
for(i=2;i<n;i++)
{
if(n%i==0)
{
flag=0;
break;
}

}
flag=1;
return flag;

}

int main()
{
int num,dif,min;
int i,j,k;
scanf("%d",&num);
min=num;
for(i=1;i<=num/2;i++)
{
j=num-i;
//i,j都是素数
if(flag(i)==1 && flag(j)==1)
{
dif=j-i;
if(dif<min)
{
min=dif;
k=i;
}
}
}
printf("%d\n%d\n",k,num-k);

return 0;


}

发表于 2022-06-08 20:20:00 回复(1)

C

baixu

#include<stdio.h>

int main() {
int val;
int num[1000];
scanf("%d", &val);
int i, j;
int pre;
int next;
int max = 10000;
int k = 0;
//得到素数
for (i = 1; i <= val; i++) { //1是素数从2开始
int flg = 0;
for (j = 2; j < i; j++) { //和2-本身-1取余有0则不为素数
if ((i % j) == 0) {
flg = 1; //不是素数
}
}
if (flg == 0) {
num[k++] = i;
if (val == (i * 2)) {
num[k++] = i;
}
}
}
//比较组合找到最小的素数之差
for (int i = 1; i < k; i++) {
for (int j = i + 1; j < k; j++) {
if (num[i] + num[j] == val) {
if ((num[j] - num[i]) < max) {
max = num[j] - num[i];
pre = num[i];
next = num[j];
}
}
}
}
printf("%d\n", pre);
printf("%d\n", next);
return 0;
}

发表于 2022-04-05 10:54:10 回复(0)

C

viod

简单题提交几次才过，第一次通过率42%，第二次81%，第三次100%。总结就是情况没有考虑全面，提交看到没通过的测试用例才恍然大悟，做题还是得想多一点才行。

#include<stdio.h>

int isPnumber(int n){
    for(int i=2;i<n;i++){
        if(n%i==0) return 0;
        else if(i==n-1) return n;
    }return 0;  //for循环内是条件分支时需要在循环外加上return出口，返回值可以是任意值代表异常，否则编译器会警告，因为循环不可预测，需要正常出口和异常出口。
}

int main(){
    int n;
    while(~scanf("%d",&n)){
        if(n==4) { printf("2\n2\n"); break; }  //特殊情况直接输出结果
        int mid=n/2;
        int low=0,high=0;
        for(int j=1;(low==0)||(high==0)||(low+high!=n);j++){
             if(isPnumber(mid-j)) low=mid-j;
             if(isPnumber(mid+j)) high=mid+j;
        }
        if(isPnumber(mid))
            printf("%d\n%d\n",mid,mid);   //偶数的中间数为刚好素数的情况

        else printf("%d\n%d\n",low,high);
    }
}

发表于 2022-03-31 04:30:01 回复(0)

C

牛客991584878号

#include<stdio.h>
int main()
{
    int a=0;
    int i=0;
    while(scanf("%d",&a)!=EOF)
    {
       for(i=a/2;i>=2;i--)
        { 
    //       printf("%d",sushu(i));
        
            if(sushu(i)==0&&sushu(a-i)==0)
            {
               printf("%d\n",i);
               printf("%d\n",a-i);
                break ;
            }
        }
    }
}

int sushu(int i)
{
    int flag=0;              //flag=0,为素数，1为非素数
    int j=0;
    for(j=2;j<i;j++)
    {   
        if(i%j==0)
        {
            flag=1;
            break ;
        }
    }
    if(flag==0) return 0;
    else 
        return 1;
}

发表于 2021-11-16 23:24:06 回复(0)

C

致爱丽丝

先求得SIZE内的所有素数，再查表即可

查表从输入的偶数的半值开始向下查找，当两个值都是素数时即满足。

#include <stdio.h>
#include <math.h>

#define SIZE 1000

int prime[SIZE+1];

void getprime(void);
void checknum(int num);

int main(void)
{
    int num;
    getprime();
    while(scanf("%d",&num)!=EOF){
        checknum(num);
    }
    return 0;
}

void getprime(void)
{
    int i,j,tmp,flag;
    prime[1] = 1,prime[2] = 1,prime[3] = 1;
    for(i=5; i<=SIZE; i+=2){        //偶数不是素数
        tmp = sqrtf(i);
        flag = 1;
        for(j = 3; j <= tmp; j+=2){    //被除数不是偶数
            if(i % j == 0) flag = 0;
        }
        if(flag) prime[i] = 1;
    }
}

void checknum(int num)
{
    int half,i,j;
    for(i = num/2;i>=1;i--){
        j = num - i;
        if(prime[i] && prime[j]){
            printf("%d\n%d\n",i,j);
            break;
        }
    }
}

发表于 2021-11-09 14:53:00 回复(0)

C

牛客847677727号

#include <stdio.h>



int issushu(int m)
{
    int i;
    int k;
    k=(int)sqrt( (double)m );
    for(i=2;i<=k;i++)
        if(m%i==0)
            break;
    if(i>k)
        return 1;
    else
        return 0;
}


int main()
{
    int N;
    int i,j;
    while(scanf("%d",&N)!=EOF)
    {
        int flag=0;
        for (i=N/2;i<=N;i++)
        {
            if (issushu(i))
            {
                for (j=N/2;j>=0;j--)
                {
                    if (issushu(j))
                    {
                        if (i+j==N)
                        {
                            printf("%d\n",j);
                            printf("%d\n",i);
                            flag=1;
                        }
                    }
                    if (flag==1)
                        break;
                }
            }
            if (flag==1)
                break;
        }
    }
}

发表于 2021-10-30 21:39:26 回复(0)

C

80后大叔

笨办法做出来了，楼下的答案更优化一点

#include<stdio.h>
#define len 100
// 遍历获取所有的素数
int getSS(int ss[len], int in) {
    ss[0] = 1;
    ss[1] = 3;
    int dest = 2;
    if(in > 4) {
        for(int i = 5; i <= in; i+=2) {
            int isSS = 0;
            for(int j = 2; j < i; j++) {
                if(i%j == 0) {
                    isSS = -1;
                    break;
                }
            }
            if(isSS == 0) {
                ss[dest] = i;
                dest++;
            }
        }
    }
    return dest;
}
int main() {
    int in;
    while(scanf("%d\n", &in) != EOF) {
        int ss[len] = {0};
        int lenOfSS = getSS(ss, in);
        int b = in, a = 0;
        // 找出素数差值最小的1组
        for(int i = 0; i < lenOfSS; i++) {
            for(int j = lenOfSS/2; j < lenOfSS; j++) {
                if(ss[i] + ss[j] == in) {
                    if((b - a > ss[j] - ss[i]) && (ss[j] - ss[i] >= 0)) {
                        b = ss[j];
                        a = ss[i];
                    }
                    break;
                }
            }
        }
        printf("%d\n%d\n", a, b);
    }
}

发表于 2021-08-21 11:09:17 回复(0)

查找组成一个偶数最接近的两个素数

输入描述:

输出描述:

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题