計算L和R之間至少有一個素數因子在1到50之間的數字

Question

給定L和R非常大的數字（10^18），我如何找到L和R之間的數字計數，使得數字至少有一個素數從1因素N.

注：N可爲MAX 50

Answer 1

我將僅繪製的方法，未詳細工作出來。

如果R-L很小，最好一個一個嘗試一下。

否則使用inclusion exclusion principle：出於解釋的原因，我只考慮質數2,3和5.確定有多少個數可以除以2,3,5（即其中一個質數），6,10,15 （即兩個素數）和30（即所有三個素數）。對於除數k這大約是(R-L)/k，考慮到邊界條件，我們可以得到確切的計數。調用相應的計數c（k）。

現在的數字由至少一個黃金分割的總數爲：

c(2)+c(3)+c(5)-c(6)-c(10)-c(15)+c(30)