首页 > 代码库 > HDU 5108Alexandra and Prime Numbers（大素数）

HDU 5108Alexandra and Prime Numbers（大素数）

2024-08-03 21:06:11   217人阅读

Problem Description
Alexandra has a little brother. He is new to programming. One day he is solving the following problem: Given an positive integer N, judge whether N is prime.
The problem above is quite easy, so Alexandra gave him a new task: Given a positive integer N, find the minimal positive integer M, such that N/M is prime. If such M doesn‘t exist, output 0.
Help him!
 

Input
There are multiple test cases (no more than 1,000). Each case contains only one positive integer N.
N≤1,000,000,000.
Number of cases with N>1,000,000 is no more than 100.
 

Output
For each case, output the requested M, or output 0 if no solution exists.
 

Sample Input
3
4
5
6
 

Sample Output
1
2
1
2
 


对于此题，我只想说自己好傻的，对于一个大数n,求最小的m是的n/m是素数


首先  n=素数*素数*素数......


那么我们求最大的素数，还有这个素数中不可能有两个大于sqrt（n）的，那么代码如下


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>

#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define MID(x,y) ((x+y)>>1)

using namespace std;
typedef __int64 ll;

#define N 100000

ll a[N],b[N];
ll k;

void inset()
{
	int i,j;
	a[0]=1;
	for(i=2;i<N;i++)
		if(!a[i])
		{
			for(j=i*2;j<N;j+=i)
			    a[j]=1;
			b[k++]=i;
		}

}

int main()
{
	int i,j;

	inset();
	ll n,temp;
	while(~scanf("%I64d",&n))
	{
		if(n==1)
		{
			printf("0\n");
			continue;
		}

		int flag=0;
        temp=n;
		ll m=(ll)(sqrt(n))+1;

        ll ans=0;

		for(m;m>1;m--)
			if(n%m==0)
		  {
			 while(n%m==0&&!a[m])
				n/=m;

			 if(!a[m])
			 {
			 	ans=max(ans,m);
			 }
		  }
		ans=(ll)max(ans,n);
		printf("%I64d\n",temp/ans);
	}
	return 0;
}




HDU 5108Alexandra and Prime Numbers（大素数）


联系
我们