当前位置:网站首页>An explanation of the Goldbach conjecture (upgraded version) in loco p1579

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

2021-01-13 01:48:15 osc_ yim3173g

Luogu P1579 Goldbach conjectures ( Upgraded version ) Answer key

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

 Insert picture description here

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[0]=a[1]=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[20005];
int b[20005];
int cnt=0;
void prime(int n)
{
	a[0]=a[1]=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;
	}
}

版权声明
本文为[osc_ yim3173g]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/01/20210111095609944x.html