用素数对数字进行计数

Question

给定一个数N，我需要找到从1到N至少有一个素数（2,3,5或7）的数的计数。

现在N可以高达10^18。解决这个问题的最佳方法是什么。

例句：设N=100，答案是64。

请帮助解决这个问题。

代码：这是主要功能，但显然不是好方法

    long long int n;
    cin>>n;
    long long int count=0;
    for(int i=1;i<=n;i++){
        long long temp=i;
        while(temp>0){
            int rem=temp%10;
            if(rem==2 || rem==3 ||rem==5 || rem==7){
                count++;
                break;
            }
            temp=temp/10;
        }
    }

Answer 1

你认为这个问题需要编程！！

用数学来回答。

考虑互补问题，即数字中没有素数。因此只能使用数字{0,1,4,6,8,9}。

例如，你可以用这一套产生多少个2位数的数字？答案是6*6=6^2=36。如果n是100，则答案是100-36=64。

在一个简单的情况下，如果N是10的幂，那么答案是n-6^log(N)。

那么n不是10的幂。考虑n=57。在这种情况下，当第一个数字低于5时。您可以将{0,1,4}用于第一个数字，将{0,1,4,6,8,9}用于第二个数字。答案是57-3*6+1=40。（主题中排除了零，所以答案是递增的）。