An explanation of the Goldbach conjecture (upgraded version) in loco p1579

2021-01-13 01:48:15

This is the first time that Ben konjac has ever solved the problem , I hope the gods will correct me .

The original question is shown in the picture Now let's analyze the problem , The data strength of this question is not big, only 20000, The time limit is 1s, Memory is limited to 125M. Of course, if you want to use general exhaustion to judge prime numbers, it will time out , So we use the sieve method to judge prime numbers .

\\ This is the subfunction of the sieve
void prime(int n)
{
a=a=true;
for(int i=2;i<=n;i++)  \\ If a number is prime , Then the multiples of this number must be composite numbers
if(!a[i])             \\ When a[i] by false Time description i Prime number
{
b[cnt++]=i;
for(int j=i*i;j<=n;j+=i) \\ Mark i A multiple of is a composite number
a[j]=true;
}
}

Now attached AC Code

#include<bits/stdc++.h> \\ All powerful
using namespace std;
bool a;
int b;
int cnt=0;
void prime(int n)
{
a=a=true;
for(int i=2;i<=n;i++)
if(!a[i])
{
b[cnt++]=i;
for(int j=i*i;j<=n;j+=i)
a[j]=true;
}
}
int main (void)
{
int n,flag=0;
scanf("%d",&n);
prime(n);
for(int i=0;i<cnt;i++)    \\ Double cycle exhausts
{
for(int j=0;j<cnt;j++)
if(!a[n-b[i]-b[j]]&&n-b[i]-b[j]>0)
{
flag=1; \\ Judge that you have found the right combination
printf("%d %d %d",b[i],b[j],n-b[i]-b[j]);
break;
}
if(flag) \\ If you've found the right combination, jump out of the loop
break;
}
}

https://chowdera.com/2021/01/20210111095609944x.html