题目72：分母不超过一百万的最简真分数的集合中包含多少元素？
Counting fractionsConsider 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 于 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 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 + 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 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;
}
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]