a***e
发帖数: 30 | 1 A positive integer is said to be squarefree if it is divisible by no perfect
square larger than 1. For example, the first few squarefree numbers are {1,
2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, …}. Find the nth smallest
squarefree number. Note n can be very large such as 1M. | g**********y
发帖数: 14569 | 2 直接用筛法，brutal force就很快。对1M, 16ms; 100M, 也就2s. | g**********y
发帖数: 14569 | 3 public long find(int N) {
boolean[] a = new boolean[2*N];
for (int i=2; i*i < 2*N; i++) {
int t = i*i;
for (int j=t; j < 2*N; j+=t) {
a[j] = true;
}
}
int count = 0;
for (int i=1; i<2*N; i++) {
if (!a[i]) count++;
if (count == N) return i;
}
return -1;
} | d****3
发帖数: 93 | 4 binary search
perfect
1,
【在 a***e 的大作中提到】
: A positive integer is said to be squarefree if it is divisible by no perfect
: square larger than 1. For example, the first few squarefree numbers are {1,
: 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, …}. Find the nth smallest
: squarefree number. Note n can be very large such as 1M.
| g**********y
发帖数: 14569 | 5 Can you explain more or post your code here?
【在 d****3 的大作中提到】
: binary search
:
: perfect
: 1,
| m**q
发帖数: 189 | 6 为什么只算前2*N个呢？
刚查了一下，平方倒数和 1^2 + (1/2)^2 + (1/3)^2 +...+ (1/n)^2
的极限是 π²/6，大约1.64的样子，减去1，大约是0.64，说明前N个
数中大约有0.64*N个可以是能被平方整除的。那么，要获得N个squarefree
的数，至少要3*N个数才够啊
求解答
【在 g**********y 的大作中提到】
: public long find(int N) {
: boolean[] a = new boolean[2*N];
: for (int i=2; i*i < 2*N; i++) {
: int t = i*i;
: for (int j=t; j < 2*N; j+=t) {
: a[j] = true;
: }
: }
: int count = 0;
: for (int i=1; i<2*N; i++) {
|
|
