用黄金数字计算数字

Question

给定数量NI需要找到从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.(在主要问题中排除零,因此答案增加了).