感谢此大佬的博客：https://blog.csdn.net/codeswarrior/article/details/81263050 写的非常好！
题意：
给出公式Gcd(n)=gcd(C(n,1),C(n,2),……,C(n,n-1)
其中C(n,1)代表组合C，n选1，等于n！/1！/(n-1)!
让求f(n)=Gcd(3)+Gcd(4)+…+Gcd(i)+…+Gcd(n)
输入N，求f(n)
分析：
最暴力的做法，就是写一个组合计算函数F(c)，依次把1到100W的gcd算出来.......
暴力终究是暴力，不能解决一切，参考了别人的博客，仔细推理了一下，还真成立
对于G=gcd(C(n,1),C(n,2)，C(n,3)...C(n,n-1) )来说
有且仅有以下三种情况：
(1) 如果n为素数，G=nG=n
(2) 如果n有两个或两个以上的素因子，G=1G=1
(3) 如果n只有一个素因子pp，G=p
证明过程见上面博客。
我们先把1到100W的素数筛选出来，放入prime数组，也顺带放入isprime数组可以方便后续o(1)判断是否素数
有几点需要注意的地方：
1.输入N>=3，不需要考虑小于3的数。
2.判断素因子个数的时候，没有从i=2开始到sqrt(x)，而是从prime素数堆中遍历，大大的省时。这点我刚开始没想到
3.if (sum == 1 && x == 1)代表素因子唯一
(sum == 1 && x > 1)代表素因子不唯一
1. #include<iostream> 2. #include<algorithm> 3. #include<cstring> 4. using namespace std; 5. bool isprime[1000010]; 6. int prime[100000], len; 7. long long fx[1000001]; 8. int dd(int x) { 9. int sum = 0; 10. int cnt = -1; 11. for (int i = 0; i < len && prime[i] * prime[i] <= x; i++) { 12. if (x % prime[i] == 0) { 13. cnt = prime[i]; 14. sum++; 15. if (sum > 1) return 1; 16. while (x % prime[i] == 0) { 17. x /= prime[i]; 18. } 19. } 20. } 21. if (sum == 1 && x == 1) return cnt; 22. if (sum == 1 && x > 1) return 1; 23. return 1; 24. } 25. void init() { 26. memset(isprime, true, sizeof(isprime)); 27. len = 0; 28. for (int i = 2; i < 1000001; i++) { 29. if (isprime[i]) { 30. prime[len++] = i; 31. for (int j = i + i; j <= 1000001; j += i) { 32. isprime[j] = false; 33. } 34. } 35. } 36. fx[2] = 0; 37. for (int i = 3; i <= 1000000; i++) { 38. if (isprime[i]) fx[i] = fx[i - 1] + i; 39. else fx[i] = fx[i - 1] + dd(i); 40. } 41. } 42. int main() 43. { 44. init(); 45. int n; 46. while (~scanf_s("%d", &n)) { 47. printf("%lld\n", fx[n]); 48. } 49. return 0; 50. }
