不是VIP会员，不能显示答案

题目解答

题目： 
#include <cstdio>


#include <cmath>


const int N = 1e9;


int isnp[50005],p[50005],pcnt;





inline void getPrime(const int n = sqrt(N)) {


	isnp[0]= isnp[1]=1;


	for (register int i=2; i<=n; ++i) {


		if (!isnp[i]) p[pcnt++]=i;


		for (register int j=0; i*p[j]<=n && j<pcnt; ++j) {


			isnp[i*p[j]]=1;


			if (!(i% p[j])) break ;


		}


	}


}





int main() {


	getPrime();	int n;


	while (scanf(" %d", &n) && n) {


		int _sqrt = sqrt(n),ans= n;


		for (register int j = 0; p[j]<=_sqrt && j<pcnt; ++j) {


			if (n % p[j]==0) {


				while (n % p[j]==0)n/=p[j];


				ans = 1ll * ans *(p[j]-1)/ p[j];


			}


		}


		if (n!=1) ans = 1ll* ans * (n-1)/n;


		printf("%d\n", ans);


	}


	return 0;


}


判断题

1) 若去掉第12行，程序也能得到正确结果。()

2) 若去掉第23行，程序也能得到正确结果。()

3) 若输入的 n≤10^8，则第10行j<pcnt条件可以省略。()

4) 若输入的 n≤10^8，则第21行j<pcnt条件可以省略。()


选择题

5) 当n=504时，输出ans 为() 。

6) getPrime函数的时间复杂度是( ) 。
考点：
分析：
解答：
评论：
老师：