NYOJ-520 最大素因子【數論】

題目連接：http://acm.nyist.net/JudgeOnline/problem.php?pid=520php

解題思路：ios

簡單的模擬題，有2種思路：spa

第一種暴力：.net

直接找到n的最大的素因子，而後找出最大素因子在素數表中出現的位置便可。code

第二種：get

在篩素數的同時進行處理，由於第二層須要更新能夠整除prim[i]，即當前最大素因子，因此能夠在此更新。一次打表便可。string

代碼以下：it

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;

#define N 1000010
int prim[N];
int ans[N];

void fun()
{
	int limit = sqrt(N * 1.0);
	memset(prim, 0, sizeof(prim));
	memset(ans, 0, sizeof(ans));
	for(int i = 2; i <= limit; ++i)
		if(!prim[i])
			for(int j = i * i; j < N; j += i)
				prim[j] = 1;
	int num = 0;
	for(int i = 1; i < N; ++i)
		if(!prim[i])
			ans[i] = num++;
	int temp = 0;
	for(int i = 2; i < N; ++i)
		if(!prim[i])
			prim[temp++] = i;
}

int prim_induce(int n)
{
	if(n == 1)
		return 1;
	int maxprim = 1;
	for(int i = 0; prim[i] * prim[i] <= n; ++i)
	{
		if(n % prim[i] == 0)
		{
			maxprim = max(maxprim, prim[i]);
			while(n % prim[i] == 0)
				n /= prim[i];
		}
		if(n == 1)
			break;
	}
	if(n != 1)
		return n;
	else
		return maxprim;
}

int main()
{
	int n;
	fun();
	while(~scanf("%d", &n))
		printf("%d\n", ans[prim_induce(n)]);
	return 0;
}

代碼以下：io

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;

#define N 1000010
int prim[N];

void fun()
{
	for(int i = 2, temp = 0; i < N; ++i)
		if(!prim[i])
		{
			temp++;
			for(int j = i; j < N; j += i)
				prim[j] = temp;
		}
}

int main()
{
	int n;
	fun();
	while(~scanf("%d", &n))
		printf("%d\n", prim[n]);
	return 0;
}