Something about prime number in acmicpc.

First,the way to determine a prime is sieve except the brute force algo(just enumerate to n^0.5)

never look down to this algo,it can yield some interesting problems.

for (i=2;i<=maxn;i++)

{
if (!is[i])
{
prime[pl++]=i;
if (1LL*i*i>1LL*maxn) continue;
for(j=i*i;j<=maxn;j+=i)is[j]=1;
}
}

the simple code it's here

although short,i think the time is enough(generate prime number from 1 to 10000000 only in 0.9sec.).

http://acm.scs.bupt.cn/onlinejudge/showproblem.php?problem_id=1514this problem is good for sieve,and if you don't know Wilson's theorem,just google it.

the principle of it is that any composite number must have a minimum prime factor.

in the same way as sieve,we can work out the eular function of numbers.

The number of positive integers, not greater than n, and relatively prime with n, equals to Euler’s totient function φ (n). In symbols we can state that φ (n) ={a Î N: 1 ≤ a ≤ n, gcd(a, n) = 1} This function has the following properties: If p is prime, then φ (p) = p – 1 and φ (pa) = p a * (1 – 1/p) for any a. If m and n are coprime, then φ (m * n) = φ (m) * φ (n). If n = , then Euler function can be found using formula: φ (n) = n * (1 – 1/p 1) * (1 – 1/p 2) * ... * (1 – 1/p k) for example:φ(12)=12*(1-1/2)(1-1/3)=4。 we can use a method similar to sieve. for (i=2;i { if (!is[i]) { prime[pl++]=i; if (1LL*i*i>1LL*maxn) continue; for(j=i*i;j } } phi[1]=0; for (i=2;i<=maxn;i++)phi[i]=i; for (i=2;i<=maxn;i++) { if (!is[i]) { for (j=i;j<=maxn;j+=i) { phi[j]=(phi[j]/i)*(i-1); } } } example http://acm.tju.edu.cn/toj/showp3300.html you can also find the number of divisors of a number. x=p1^a1*...* pi^ai by the multiply principle ans=(a1+1)*...*(ai+1) for (i=2;i { if (!is[i]) { prime[pl++]=i; if (1LL*i*i>1LL*maxn) continue; for(j=i*i;j } } for (i=1;i<=maxn;i++)fac[i]=1; for (i=2;i<=maxn;i++) { if (!is[i]) { fac[i]=2; for (j=2*i;j<=maxn;j+=i) { int tmp=j,s=0; while (tmp%i==0) { s++;tmp/=i; } fac[j]*=(s+1); } } } http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3286 some problem which relevant to number prime factorization can solve by the variation of sieve,not list them all.