发一个projecteuler上的题 Strong Achilles Number

gracias

原题链接 ：http://projecteuler.net/problem=302 A positive integer n is powerful if p2 is a divisor of n for every prime factor p in n. A positive integer n is a perfect power if n can be expressed as a power of another positive integer. A positive integer n is an Achilles number if n is powerful but not a perfect power. For example, 864 and 1800 are Achilles numbers: $864=2^5*3^3$ and $1800=2^3*3^2*5^2$. We shall call a positive integer S a Strong Achilles number if both S and φ(S) are Achilles numbers.1 For example, 864 is a Strong Achilles number: $\phi(864)=288=2^5*3^2$. However, 1800 isn't a Strong Achilles number because: $\phi(1800) =480=2^5*3^1*5^1$. There are 7 Strong Achilles numbers below 104 and 656 below 108. How many Strong Achilles numbers are there below $10^18$? 1 φ denotes Euler's totient function. 我用程序验证了一下10^8以下的情况分布如下,更大范围内就没有有效办法了.不知各位高手有没有兴趣讨论讨论. 我验证的结果:如下 1 th StrongAchilles number :500 2 th StrongAchilles number :864 3 th StrongAchilles number :1944 4 th StrongAchilles number :2000 5 th StrongAchilles number :2592 6 th StrongAchilles number :3456 7 th StrongAchilles number :5000 7 StrongAchilles numbers less than 10000 34 StrongAchilles numbers less than 100000 99 StrongAchilles numbers less than 1000000 260 StrongAchilles numbers less than 10000000 656 StrongAchilles numbers less than 100000000

mathe

对于Strong Achilles Number,其最大素因子的次数至少3次，这个可以用来大大减小搜索范围

gracias

的确能减小搜索范围,试一下.

gracias

找出来了,我的程序要跑8分钟才能找完

mathe

另第一个个StrongAchilles应该是$3^4*2^2=324$而不是500吧

gracias

3^4*2^2 = (2*3^2)^2 不是strongachilles number