站长百科 题解UVA10948 The primary problem 正文

题解UVA10948 The primary problem

2022-12-09,,

前言

前置

\(\sf{Solution}\)

既然有了 \(n\) ，那找出 \(a\) 和 \(b\) 就只要枚举 \(a\) 的范围 \(1\sim n\)，判断 \(a\) 和 \(n-a\) 是否为质数.

因为 \(a\) 和 \(b\) 都不为负数，所以可以缩小枚举范围为 \(1\sim \dfrac{n}{2}\) .

至于判质数，相信欧拉筛能解决问题.

欧拉筛相关（请忽略中二部分

\(\sf{Code}\)

#include<iostream>

using namespace std;

int n,ans,prime[5000005];

bool visit[10000005];

int main()

{

	ios::sync_with_stdio(false);

	visit[1]=true;//初始化

	for(int i=2;i<=10000000;++i)

	{

		if(!visit[i])

			prime[++ans]=i;

		for(int j=1;prime[j]*i<=10000000&&j<=ans;++j)

		{

			visit[i*prime[j]]=true;

			if(!(i%prime[j]))

				break;

		}

	}//欧拉筛

	while(cin>>n&&n!=0)

	{

		bool flag=false;//别忘了初始化

		cout<<n<<":\n";

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

		{

			int a=i,b=n-i;

			if(!visit[a]&&!visit[b])

			{

				cout<<a<<"+"<<b<<"\n";

				flag=true;//有解标记

				break;

			}

		}

		if(!flag)

			cout<<"NO WAY!\n";//无解

	}

	return 0;

}

题解UVA10948 The primary problem的相关教程结束。

《题解UVA10948 The primary problem.doc》

下载本文的Word格式文档，以方便收藏与打印。

Copyright 2023. 昆居客 - IT编程,互联网信息技术文档大全!