21/02/27 17:42:11.37 FEnpOKY/.net
>>247
俺みたいなボンクラは互いに素な合成数を数え上げていく方法
しか思いつかん。
１～Nまでの自然数で、最大の素因数がpとなるpの倍数の個数
をf(N,p)とすると、pの倍数の個数は[N/p]で、p✕1～p✕[N/p]
となるので、この中から2,3,5..とpより小さい素数の倍数と
なるものを除けばよい。したがって、
f(N,p)=[N/p] - f([N/p],2) -f([N/p],3) - f([N/p],5)...
よって、
f(1000,2)=[1000/2]=500
f(1000,3)=[1000/3]-f([1000/3],2)=333-[333/2]=167
f(1000,5)=[1000/5]-f([1000/5],2)-f([1000/5],3)
=200-[200/2]-{[200/3]-f([200/3],2)}
=200-100-(66-[66/2])=67
f(1000,7)=[1000/7]-f([1000/7],2)-f([1000/7],3)-f([1000/7],5)
=142-[142/2]-{[142/3]-f([142/3],2)}-{[142/5]-f([142/5],2)-f([142/5],3)}
=142-71-(47-[47/2])-{28-[28/2]-([22/3]-f([22/3],2)}
=142-71-(47-23)-{28-14-(7-3)}=37
1～1000の間にある2,3,5,7の倍数の個数はこれらの総和なので、500+167+67+37=771
素数である2,3,5,7を除けば、この範囲に少なくとも771-4=767個の合成数が存在すること
になり、素数の数は233個以下となる。
泥臭いけど,f(1000,31)までの和をとってやればすべての素数の個数が求まる。