素数筛，单点的欧拉函数，筛法求欧拉函数

本文主要是介绍素数筛，单点的欧拉函数，筛法求欧拉函数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

返回了在素数的个数、

int prime[maxn] , vis[maxn] ;
int sieve(int n)
{
int m = (int)sqrt(n+0.5) , i , j ;
for(i = 2 ; i <= m ; i++)
if( !vis[i] ) i
{
for(j = i*i ; j <= n ; j += i)
vis[j] = 1 ;
}
j = 0 ;
for(i = 2 ; i <= n ; i++)
if( !vis[i] )
prime[j++] = i ;
return j ;
}

 

单点的欧拉函数

欧拉函数表示了，小于n的所有正整数并且和n互质的个数

 

int euler_phi(int n)
{
int m = (int)sqrt(n+0.5);
int ans = n , i ;
for( i = 2 ; i <= m ; i++)
{
if( n%i==0 )
{
ans = ans / i * (i-1);
while( n%i==0 )
n /= i ;
}
}
if( n > 1 )
ans = ans / n * ( n-1 );
return ans ;
}

 

 

筛法更新一段的phi

int euler_phi(int n)
{
int m = (int)sqrt(n+0.5);
int ans = n , i ;
for( i = 2 ; i <= m ; i++)
{
if( n%i==0 )
{
ans = ans / i * (i-1);
while( n%i==0 )
n /= i ;
}
}
if( n > 1 )
ans = ans / n * ( n-1 );
return ans ;
}

 

这篇关于素数筛，单点的欧拉函数，筛法求欧拉函数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---