欧拉计划 发表于 2015-11-5 16:25:21

题目72:分母不超过一百万的最简真分数的集合中包含多少元素?

Counting fractions

Consider the fraction, n/d, where n and d are positive integers. If n<d and HCF(n,d)=1, it is called a reduced proper fraction.

If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we get:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

It can be seen that there are 21 elements in this set.

How many elements would be contained in the set of reduced proper fractions for d ≤ 1,000,000?
题目:

考虑分数 n/d, 其中 n 和 d 是正整数。如果 n<d 并且最大公约数 HCF(n,d)=1, 它被称作一个最简真分数。

如果我们将 d ≤ 8 的最简真分数按照大小的升序列出来,我们得到:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5 , 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

可知该集合中共有 21 个元素。

d ≤ 1,000,000 的最简真分数集合中包含多少个元素?

jerryxjr1220 发表于 2016-10-16 13:49:59

本帖最后由 jerryxjr1220 于 2017-10-12 10:55 编辑

这题其实也是欧拉函数的扩展。
欧拉函数phi(n)定义了小于n的正整数与n互质的个数。
那么sum(phi(2~8))=21
同样,本题就是求解sum(phi(2~1000000)){:5_95:}

from time import clock
start = clock()

def getPrime(n):
    primes = *n
    primes, primes = False, False
    for (i, prime) in enumerate(primes):
      if prime:
            for j in range(i*i,n,i):
                primes = False
    primelist = []
    for (k, trueprime) in enumerate(primes):
      if trueprime:
            primelist.append(k)
    return primelist

def philist(n):
    primelist = getPrime(n)
    PHI = *(n+1)
    for eachprime in primelist:
      PHI = eachprime - 1
    for i in range(len(primelist)):
      p = primelist
      for k in range(p*p,n+1,p):
                PHI = PHI*(p-1)
      for j in range(p*p,n+1,p*p):
            PHI = PHI*p
    return PHI
plist = philist(1000000)

print(sum(plist))

end = clock()
print ('Time:%.3f sec' % (end-start))
303963552391
Time: 4.211 sec

久疤K 发表于 2018-6-26 19:44:57

jerryxjr1220 发表于 2016-10-16 13:49
这题其实也是欧拉函数的扩展。
欧拉函数phi(n)定义了小于n的正整数与n互质的个数。
那么sum(phi(2~8 ...

厉害!!
但是过程有瑕疵:
def philist(n):
    primelist = getPrime(n)
    # 上面获取质数时要变成getPrime(n+1)
检验:
r(11) == r(10) + 10
而你的却是
r(11) == r(10)
因为在边界处恰好为质数, 你没有获取到, 造成phi = 0
上面的BUG只有在边界为质数时显示.
另外, 共享个比较高效的获取质数的方法:def get_primes( n ):
    t = list(range(3,n,2))
    for i in range(len(t)):
      if t:
            t::t] = * len( t::t] )
    return +

fc1735 发表于 2019-12-19 11:11:09

P = []
L = list(range(1000001))
for i in range(2, len(L)):
if L == i:
    P.append(i)
    L = i - 1
for p in P:
    if i * p >= len(L):
      break
    if i % p == 0:
      L = L * p
      break
    L = L * (p - 1)

L = 0
print(sum(L))

基于线性筛的方法
https://github.com/devinizz/project_euler/blob/master/page02/72.py

debuggerzh 发表于 2020-9-3 10:25:37

303963552391

Process returned 0 (0x0)   execution time : 0.064 s
Press any key to continue.
线性筛打表,欧拉函数递推(来自2#69题的方法)
#include<iostream>
#include<cmath>
using namespace std;

const int M = 1e6;
int ct = 0;
bool prime;
int factor;
int phi = {0};

void euler_sieve(){
prime = false;
for (int i = 2;i <= M;i++) prime = true;

for (int i = 2;i <= M;i++){
    if (prime) {factor[++ct] = i;phi = i-1;}
    for (int j = 1;j <= ct && i*factor < M;j++){
      prime] = false;
      if (i % factor == 0) break;
    }
}
}

void ini(){
for (int i = 2;i <= sqrt(M);i++){
    if (prime){
      for (int j = i;j*i <= M;j++)
      if (j % i == 0) phi = phi * i;
      else            phi = phi * (i-1);
    }
}
}

int main(){
unsigned long long ans = 0;
euler_sieve();ini();

for (int d = 2;d <= M;d++)
    //cout << phi << endl;
    ans += phi;

cout << ans << endl;
return 0;
}

永恒的蓝色梦想 发表于 2021-6-23 23:33:14

C++ 20ms#include<iostream>
#include<vector>
#include<cstring>



int main() {
    using namespace std;
    ios::sync_with_stdio(false);

    constexpr unsigned int UPPER_BOUND = 1000000;
    static bool is_prime;
    static unsigned int phi;
    vector<unsigned int> primes;
    unsigned int i, k;
    unsigned long long result = 0;

    memset(is_prime, -1, UPPER_BOUND);
    is_prime = is_prime = 0;


    for (i = 2; i < UPPER_BOUND; i++) {
      if (is_prime) {
            primes.push_back(i);
            result += phi = i - 1;
      }

      for (unsigned int j : primes) {
            k = i * j;

            if (k >= UPPER_BOUND) {
                break;
            }

            is_prime = false;

            if (!(i % j)) {
                result += phi = phi * j;
                break;
            }

            result += phi = phi * (j - 1);
      }
    }


    cout << result << endl;
    return 0;
}
页: [1]
查看完整版本: 题目72:分母不超过一百万的最简真分数的集合中包含多少元素?