用于多重评估的优化Euler Toticent函数-yiteyi-C++库

E 乌勒 T 奥廷特 F ETF（ETF）输入n的Φ（n）是{1，2，3，…，n}中与n相对素数的数的计数，即 GCD（最大公约数） n等于1。 例如：

null

Φ(5) = 4gcd(1, 5) is 1, gcd(2, 5) is 1, gcd(3, 5) is 1 and gcd(4, 5) is 1Φ(6) = 2gcd(1, 6) is 1 and gcd(5, 6) is 1,

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

我们讨论过计算欧拉函数的不同方法这对单一输入很有效。在需要多次调用Euler Toticent函数（如10^5次）的问题中，简单的解决方案将导致TLE（超过时间限制）。这个想法是使用埃拉托斯坦筛 . 找到所有素数的上限，比如10^5，使用埃拉托斯坦筛 . 为了计算Φ（n），我们做如下操作。

将结果初始化为n。
迭代所有小于或等于n的平方根的素数（这与简单方法不同。我们不是迭代所有小于或等于平方根的数，而是只迭代素数）。让当前素数为p。我们检查p是否除以n，如果是，我们通过重复将p除以n来删除n中所有出现的p。我们还将结果减去n/p（这许多数字的GCD不是1加n）。
最后我们返回结果。

C++

                         // C++ program to efficiently compute values                       
                         // of euler totient function for multiple inputs.                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         #define ll long long                       
                         const                                     int                                     MAX = 100001;                       
           
                         // Stores prime numbers upto MAX - 1 values                       
                         vector<ll> p;                       
           
                         // Finds prime numbers upto MAX-1 and                       
                         // stores them in vector p                       
                         void                                     sieve()                       
                         {                       
                                                 ll isPrime[MAX+1];                       
           
                                                 for                                     (ll i = 2; i<= MAX; i++)                       
                                                 {                       
                                                 // if prime[i] is not marked before                       
                                                 if                                     (isPrime[i] == 0)                       
                                                 {                       
                                                 // fill vector for every newly                       
                                                 // encountered prime                       
                                                 p.push_back(i);                       
           
                                                 // run this loop till square root of MAX,                       
                                                 // mark the index i * j as not prime                       
                                                 for                                     (ll j = 2; i * j<= MAX; j++)                       
                                                 isPrime[i * j]= 1;                       
                                                 }                       
                                                 }                       
                         }                       
           
                         // function to find totient of n                       
                         ll phi(ll n)                       
                         {                       
                                                 ll res = n;                       
           
                                                 // this loop runs sqrt(n / ln(n)) times                       
                                                 for                                     (ll i=0; p[i]*p[i] <= n; i++)                       
                                                 {                       
                                                 if                                     (n % p[i]== 0)                       
                                                 {                       
                                                 // subtract multiples of p[i] from r                       
                                                 res -= (res / p[i]);                       
           
                                                 // Remove all occurrences of p[i] in n                       
                                                 while                                     (n % p[i]== 0)                       
                                                 n /= p[i];                       
                                                 }                       
                                                 }                       
           
                                                 // when n has prime factor greater                       
                                                 // than sqrt(n)                       
                                                 if                                     (n > 1)                       
                                                 res -= (res / n);                       
           
                                                 return                                     res;                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 // preprocess all prime numbers upto 10 ^ 5                       
                                                 sieve();                       
                                                 cout << phi(11) <<                                     ""                                     ;                       
                                                 cout << phi(21) <<                                     ""                                     ;                       
                                                 cout << phi(31) <<                                     ""                                     ;                       
                                                 cout << phi(41) <<                                     ""                                     ;                       
                                                 cout << phi(51) <<                                     ""                                     ;                       
                                                 cout << phi(61) <<                                     ""                                     ;                       
                                                 cout << phi(91) <<                                     ""                                     ;                       
                                                 cout << phi(101) <<                                     ""                                     ;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to efficiently compute values                       
                         // of euler totient function for multiple inputs.                       
                         import                                     java.util.*;                       
           
                         class                                     GFG{                       
                         static                                     int                                     MAX =                                     100001                                     ;                       
           
                         // Stores prime numbers upto MAX - 1 values                       
                         static                                     ArrayList<Integer> p =                                     new                                     ArrayList<Integer>();                       
           
                         // Finds prime numbers upto MAX-1 and                       
                         // stores them in vector p                       
                         static                                     void                                     sieve()                       
                         {                       
                                                 int                                     [] isPrime=                                     new                                     int                                     [MAX+                                     1                                     ];                       
           
                                                 for                                     (                                     int                                     i =                                     2                                     ; i<= MAX; i++)                       
                                                 {                       
                                                 // if prime[i] is not marked before                       
                                                 if                                     (isPrime[i] ==                                     0                                     )                       
                                                 {                       
                                                 // fill vector for every newly                       
                                                 // encountered prime                       
                                                 p.add(i);                       
           
                                                 // run this loop till square root of MAX,                       
                                                 // mark the index i * j as not prime                       
                                                 for                                     (                                     int                                     j =                                     2                                     ; i * j<= MAX; j++)                       
                                                 isPrime[i * j]=                                     1                                     ;                       
                                                 }                       
                                                 }                       
                         }                       
           
                         // function to find totient of n                       
                         static                                     int                                     phi(                                     int                                     n)                       
                         {                       
                                                 int                                     res = n;                       
           
                                                 // this loop runs sqrt(n / ln(n)) times                       
                                                 for                                     (                                     int                                     i=                                     0                                     ; p.get(i)*p.get(i) <= n; i++)                       
                                                 {                       
                                                 if                                     (n % p.get(i)==                                     0                                     )                       
                                                 {                       
                                                 // subtract multiples of p[i] from r                       
                                                 res -= (res / p.get(i));                       
           
                                                 // Remove all occurrences of p[i] in n                       
                                                 while                                     (n % p.get(i)==                                     0                                     )                       
                                                 n /= p.get(i);                       
                                                 }                       
                                                 }                       
           
                                                 // when n has prime factor greater                       
                                                 // than sqrt(n)                       
                                                 if                                     (n >                                     1                                     )                       
                                                 res -= (res / n);                       
           
                                                 return                                     res;                       
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     main(String[] args)                       
                         {                       
                                                 // preprocess all prime numbers upto 10 ^ 5                       
                                                 sieve();                       
                                                 System.out.println(phi(                                     11                                     ));                       
                                                 System.out.println(phi(                                     21                                     ));                       
                                                 System.out.println(phi(                                     31                                     ));                       
                                                 System.out.println(phi(                                     41                                     ));                       
                                                 System.out.println(phi(                                     51                                     ));                       
                                                 System.out.println(phi(                                     61                                     ));                       
                                                 System.out.println(phi(                                     91                                     ));                       
                                                 System.out.println(phi(                                     101                                     ));                       
                                   
                         }                       
                         }                       
                         // this code is contributed by mits                       

Python3

                         # Python3 program to efficiently compute values                       
                         # of euler totient function for multiple inputs.                       
           
                         MAX                                     =                                     100001                                     ;                       
           
                         # Stores prime numbers upto MAX - 1 values                       
                         p                                     =                                     [];                       
           
                         # Finds prime numbers upto MAX-1 and                       
                         # stores them in vector p                       
                         def                                     sieve():                       
           
                                                 isPrime                                     =                                     [                                     0                                     ]                                     *                                     (                                     MAX                                     +                                     1                                     );                       
           
                                                 for                                     i                                     in                                     range                                     (                                     2                                     ,                                     MAX                                     +                                     1                                     ):                       
                                   
                                                 # if prime[i] is not marked before                       
                                                 if                                     (isPrime[i]                                     =                                     =                                     0                                     ):                       
                                   
                                                 # fill vector for every newly                       
                                                 # encountered prime                       
                                                 p.append(i);                       
           
                                                 # run this loop till square root of MAX,                       
                                                 # mark the index i * j as not prime                       
                                                 j                                     =                                     2                                     ;                       
                                                 while                                     (i                                     *                                     j <                                     =                                     MAX                                     ):                       
                                                 isPrime[i                                     *                                     j]                                     =                                     1                                     ;                       
                                                 j                                     +                                     =                                     1                                     ;                       
           
                         # function to find totient of n                       
                         def                                     phi(n):                       
           
                                                 res                                     =                                     n;                       
           
                                                 # this loop runs sqrt(n / ln(n)) times                       
                                                 i                                     =                                     0                                     ;                       
                                                 while                                     (p[i]                                     *                                     p[i] <                                     =                                     n):                       
                                                 if                                     (n                                     %                                     p[i]                                     =                                     =                                     0                                     ):                       
                                   
                                                 # subtract multiples of p[i] from r                       
                                                 res                                     -                                     =                                     int                                     (res                                     /                                     p[i]);                       
           
                                                 # Remove all occurrences of p[i] in n                       
                                                 while                                     (n                                     %                                     p[i]                                     =                                     =                                     0                                     ):                       
                                                 n                                     =                                     int                                     (n                                     /                                     p[i]);                       
                                                 i                                     +                                     =                                     1                                     ;                       
           
                                                 # when n has prime factor greater                       
                                                 # than sqrt(n)                       
                                                 if                                     (n >                                     1                                     ):                       
                                                 res                                     -                                     =                                     int                                     (res                                     /                                     n);                       
           
                                                 return                                     res;                       
           
                         # Driver code                       
           
                         # preprocess all prime numbers upto 10 ^ 5                       
                         sieve();                       
                         print                                     (phi(                                     11                                     ));                       
                         print                                     (phi(                                     21                                     ));                       
                         print                                     (phi(                                     31                                     ));                       
                         print                                     (phi(                                     41                                     ));                       
                         print                                     (phi(                                     51                                     ));                       
                         print                                     (phi(                                     61                                     ));                       
                         print                                     (phi(                                     91                                     ));                       
                         print                                     (phi(                                     101                                     ));                       
           
                         # This code is contributed by mits                       

C#

                         // C# program to efficiently compute values                       
                         // of euler totient function for multiple inputs.                       
                         using                                     System;                       
                         using                                     System.Collections;                       
                         class                                     GFG{                       
                         static                                     int                                     MAX = 100001;                       
           
                         // Stores prime numbers upto MAX - 1 values                       
                         static                                     ArrayList p =                                     new                                     ArrayList();                       
           
                         // Finds prime numbers upto MAX-1 and                       
                         // stores them in vector p                       
                         static                                     void                                     sieve()                       
                         {                       
                                                 int                                     [] isPrime=                                     new                                     int                                     [MAX+1];                       
           
                                                 for                                     (                                     int                                     i = 2; i<= MAX; i++)                       
                                                 {                       
                                                 // if prime[i] is not marked before                       
                                                 if                                     (isPrime[i] == 0)                       
                                                 {                       
                                                 // fill vector for every newly                       
                                                 // encountered prime                       
                                                 p.Add(i);                       
           
                                                 // run this loop till square root of MAX,                       
                                                 // mark the index i * j as not prime                       
                                                 for                                     (                                     int                                     j = 2; i * j<= MAX; j++)                       
                                                 isPrime[i * j]= 1;                       
                                                 }                       
                                                 }                       
                         }                       
           
                         // function to find totient of n                       
                         static                                     int                                     phi(                                     int                                     n)                       
                         {                       
                                                 int                                     res = n;                       
           
                                                 // this loop runs sqrt(n / ln(n)) times                       
                                                 for                                     (                                     int                                     i=0; (                                     int                                     )p[i]*(                                     int                                     )p[i] <= n; i++)                       
                                                 {                       
                                                 if                                     (n % (                                     int                                     )p[i]== 0)                       
                                                 {                       
                                                 // subtract multiples of p[i] from r                       
                                                 res -= (res / (                                     int                                     )p[i]);                       
           
                                                 // Remove all occurrences of p[i] in n                       
                                                 while                                     (n % (                                     int                                     )p[i]== 0)                       
                                                 n /= (                                     int                                     )p[i];                       
                                                 }                       
                                                 }                       
           
                                                 // when n has prime factor greater                       
                                                 // than sqrt(n)                       
                                                 if                                     (n > 1)                       
                                                 res -= (res / n);                       
           
                                                 return                                     res;                       
                         }                       
           
                         // Driver code                       
                         static                                     void                                     Main()                       
                         {                       
                                                 // preprocess all prime numbers upto 10 ^ 5                       
                                                 sieve();                       
                                                 Console.WriteLine(phi(11));                       
                                                 Console.WriteLine(phi(21));                       
                                                 Console.WriteLine(phi(31));                       
                                                 Console.WriteLine(phi(41));                       
                                                 Console.WriteLine(phi(51));                       
                                                 Console.WriteLine(phi(61));                       
                                                 Console.WriteLine(phi(91));                       
                                                 Console.WriteLine(phi(101));                       
           
                         }                       
                         }                       
                         // this code is contributed by mits                       

PHP

                         <?php                       
                         // PHP program to efficiently compute values                       
                         // of euler totient function for multiple inputs.                       
           
                         $MAX                                     = 100001;                       
           
                         // Stores prime numbers upto MAX - 1 values                       
                         $p                                     =                                     array                                     ();                       
           
                         // Finds prime numbers upto MAX-1 and                       
                         // stores them in vector p                       
                         function                                     sieve()                       
                         {                       
                                                 global                                     $MAX                                     ,                                     $p                                     ;                       
                                                 $isPrime                                     =                                     array_fill                                     (0,                                     $MAX                                     +1,0);                       
           
                                                 for                                     (                                     $i                                     = 2;                                     $i                                     <=                                     $MAX                                     ;                                     $i                                     ++)                       
                                                 {                       
                                                 // if prime[i] is not marked before                       
                                                 if                                     (                                     $isPrime                                     [                                     $i                                     ] == 0)                       
                                                 {                       
                                                 // fill vector for every newly                       
                                                 // encountered prime                       
                                                 array_push                                     (                                     $p                                     ,                                     $i                                     );                       
           
                                                 // run this loop till square root of MAX,                       
                                                 // mark the index i * j as not prime                       
                                                 for                                     (                                     $j                                     = 2;                                     $i                                     *                                     $j                                     <=                                     $MAX                                     ;                                     $j                                     ++)                       
                                                 $isPrime                                     [                                     $i                                     *                                     $j                                     ]= 1;                       
                                                 }                       
                                                 }                       
                         }                       
           
                         // function to find totient of n                       
                         function                                     phi(                                     $n                                     )                       
                         {                       
                                                 global                                     $p                                     ;                       
                                                 $res                                     =                                     $n                                     ;                       
           
                                                 // this loop runs sqrt(n / ln(n)) times                       
                                                 for                                     (                                     $i                                     =0;                                     $p                                     [                                     $i                                     ]*                                     $p                                     [                                     $i                                     ] <=                                     $n                                     ;                                     $i                                     ++)                       
                                                 {                       
                                                 if                                     (                                     $n                                     %                                     $p                                     [                                     $i                                     ]== 0)                       
                                                 {                       
                                                 // subtract multiples of p[i] from r                       
                                                 $res                                     -= (int)(                                     $res                                     /                                     $p                                     [                                     $i                                     ]);                       
           
                                                 // Remove all occurrences of p[i] in n                       
                                                 while                                     (                                     $n                                     %                                     $p                                     [                                     $i                                     ]== 0)                       
                                                 $n                                     = (int)(                                     $n                                     /                                     $p                                     [                                     $i                                     ]);                       
                                                 }                       
                                                 }                       
           
                                                 // when n has prime factor greater                       
                                                 // than sqrt(n)                       
                                                 if                                     (                                     $n                                     > 1)                       
                                                 $res                                     -= (int)(                                     $res                                     /                                     $n                                     );                       
           
                                                 return                                     $res                                     ;                       
                         }                       
           
                         // Driver code                       
                                   
                                                 // preprocess all prime numbers upto 10 ^ 5                       
                                                 sieve();                       
                                                 print                                     (phi(11).                                     ""                                     );                       
                                                 print                                     (phi(21).                                     ""                                     );                       
                                                 print                                     (phi(31).                                     ""                                     );                       
                                                 print                                     (phi(41).                                     ""                                     );                       
                                                 print                                     (phi(51).                                     ""                                     );                       
                                                 print                                     (phi(61).                                     ""                                     );                       
                                                 print                                     (phi(91).                                     ""                                     );                       
                                                 print                                     (phi(101).                                     ""                                     );                       
           
                         // this code is contributed by mits                       
                         ?>                       

Javascript

                         <script>                       
           
                         // Javascript program to efficiently compute values                       
                         // of euler totient function for multiple inputs.                       
           
                         var                                     MAX = 100001;                       
           
                         // Stores prime numbers upto MAX - 1 values                       
                         var                                     p = [];                       
           
                         // Finds prime numbers upto MAX-1 and                       
                         // stores them in vector p                       
                         function                                     sieve()                       
                         {                       
                                                 var                                     isPrime = Array(MAX+1).fill(0);                       
           
                                                 for                                     (                                     var                                     i = 2; i<= MAX; i++)                       
                                                 {                       
                                                 // if prime[i] is not marked before                       
                                                 if                                     (isPrime[i] == 0)                       
                                                 {                       
                                                 // fill vector for every newly                       
                                                 // encountered prime                       
                                                 p.push(i);                       
           
                                                 // run this loop till square root of MAX,                       
                                                 // mark the index i * j as not prime                       
                                                 for                                     (                                     var                                     j = 2; i * j<= MAX; j++)                       
                                                 isPrime[i * j]= 1;                       
                                                 }                       
                                                 }                       
                         }                       
           
                         // function to find totient of n                       
                         function                                     phi(n)                       
                         {                       
                                                 var                                     res = n;                       
           
                                                 // this loop runs sqrt(n / ln(n)) times                       
                                                 for                                     (                                     var                                     i=0; p[i]*p[i] <= n; i++)                       
                                                 {                       
                                                 if                                     (n % p[i]== 0)                       
                                                 {                       
                                                 // subtract multiples of p[i] from r                       
                                                 res -= parseInt(res / p[i]);                       
           
                                                 // Remove all occurrences of p[i] in n                       
                                                 while                                     (n % p[i]== 0)                       
                                                 n = parseInt(n/p[i]);                       
                                                 }                       
                                                 }                       
           
                                                 // when n has prime factor greater                       
                                                 // than sqrt(n)                       
                                                 if                                     (n > 1)                       
                                                 res -= parseInt(res / n);                       
           
                                                 return                                     res;                       
                         }                       
           
                         // Driver code                       
                         // preprocess all prime numbers upto 10 ^ 5                       
                         sieve();                       
                         document.write(phi(11)+                                     "<br>"                                     );                       
                         document.write(phi(21)+                                     "<br>"                                     );                       
                         document.write(phi(31)+                                     "<br>"                                     );                       
                         document.write(phi(41)+                                     "<br>"                                     );                       
                         document.write(phi(51)+                                     "<br>"                                     );                       
                         document.write(phi(61)+                                     "<br>"                                     );                       
                         document.write(phi(91)+                                     "<br>"                                     );                       
                         document.write(phi(101)+                                     "<br>"                                     );                       
           
                         // This code is contributed by rutvik_56.                       
                         </script>                       

输出：

10123040326072100

本文由 阿披实拉吉普特 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章