查找给定范围内的特殊数个数

Question

我无法简化这个问题的复杂度。请给我一些更好的方法。

有没有我不知道的数学公式，或者有没有更好的解决方案？

问题链接

描述：

 A special number is not divisible by any number of the form Z*Z where (Z>1).

问题：找出给定范围内的特殊数字数量。

整数限制：10^9

我这样做过：

    import math
    def special(x):
        flag=1
        i=2
        if(x==0 or x==1 or x==2):
            return 1
        while(i*i <= x):               //This is the best i can think to limit the numbers.
            if(x%(i*i)==0):
                flag=0
                break
            i=i+1
        return flag

    t=int(raw_input())
    while(t):
        x,y=map(int,raw_input().split())
        count=0
        for i in xrange(x,y+1):
            if(special(i)):
                count+=1
        print(count)
        t=t-1

Answer 1

在 special(x) 这个函数里，你只需要检查小于或等于 x 的平方根的质数。为了提高效率，我建议你提前计算出一个质数的列表（可以参考这个链接：最快的方法列出所有小于 N 的质数）。