3

我得到一个整数 N，我必须找到只能被 2,3 和/或 5 整除的前 N ​​个元素，而不能被任何其他素数整除。

例如：

N = 3
Results: 2,3,4
N = 5
Results: 2,3,4,5,6

错误数 = 55..55/5 = 11..11，这是一个素数。由于 55..55 可以被不同于 2,3 和 5 的素数整除，所以它不算数。

我想我需要一个递归函数，但我无法想象算法会是什么样子

4

4 回答 4

2

唯一只能被 2、3 或 5 整除的数是 2 i  × 3 j  × 5 k的幂i ,  j ,  k  = 0, 1, ...。

这些数字很容易生成。

于 2012-09-16T21:31:24.663 回答
2

您要查找的数字的形式为2^n * 3^m * 5^k，具有 n、m 和 k 正整数，具有n+m+k > 0.

我会预先生成一个排序数组，然后打印出第一个N.

于 2012-09-16T21:32:34.870 回答
2
于 2012-09-26T15:05:41.350 回答
0

总是有蛮力的方式：

int[] A = int[N];
int i=0;
int j=2;
while(i<N)
{
    if(j%2==0)
    {
        if(j/2==1 || A contains j/2)
        {
             A[i]=j;
             i++;
        }
    }
    else if(j%3==0)
    {
        if(j/3==1 || A contains j/3)
        {
             A[i]=j;
             i++;
        }
    }
    else if(j%5==0)
    {
        if(j/5==1 || A contains j/5)
        {
             A[i]=j;
             i++;
        }
    }
    j++;
}

对于“A 包含 X”部分，您可以在 0 到 i-1 范围内使用二进制搜索，因为 A 在那里排序。

于 2012-09-17T00:02:07.020 回答