java - 给定一个数字 n ，我们必须找出小于或等于 n 且恰好有 3 个约数的数字

Question

我使用埃拉托色尼筛法来计算具有 3 个除数且小于或等于 n 的数字，其中 n 是给定数字。

此代码的问题在于，它对 n=999999 给出答案 37386，但正确答案是 168

public static void main (String[] args) throws java.lang.Exception
{
    Scanner scn =new Scanner(System .in);
    print("enter the prime no");
    int n= scn.nextint();
    int arr[]= new int[n+1];
    for(int i=2;i<arr.length;i++)
    {
        arr[i]=1;
    }

    for(int i=2;i*i<=n;i++)
    {
        if(arr[i]==1)
        {

            for(int p=2;p*i<=n;p++)
            {
                arr[p*i]=0;
            }
        }
    }

    int count=0;
    for(int i=2;i<=n;i++)
    {
        if(arr[i]==1&&i*i<n)
        {
            count++;
        }
    }

    System.out.print(count);
}

code for calculating numbers that have exactly 3 divisors

Answer 1

埃拉托斯特尼筛法用于计算素数。您的代码正确计算出有 37386 个质数小于 999999。应该可以修改代码以查找恰好具有三个除数而不是一个除数的数字，但我会将其作为提问者的练习。