质数求法及 a trick

OO~ posted @ 2014年2月27日 20:07 in C/C++ && 算法 , 1164 阅读

  一般求质数方法就是判断数 n 在 sqrt(n) 中只存在因子 1,则 n 是素数。但是有时候这种求法在某些算法题目中时间占用太多,比较好的优化方法是使用筛选法。

求 n 以内的所有质数:

int isprime[n];

memset(isprime, 1, sizeof(isprime));

for(i = 4; i <= n; i += 2) {//筛掉大于2的偶数 
    isprime[i] = 0;
}
len = sqrt(n);
for(i = 3; i <= len; ++i) {
    if(isprime[i] == 0) {
        continue;
    }
    step = i << i; //筛掉大于质数 i 的所有非质数
    for(j = i * i; j < n; j += step) {
        isprime[j] = 0;
    }
}

  上述代码中 isprime[i] == 1 时,表示 i 即是一个质数。个人觉得代码中的精华应该是 step 的赋值

step = i << i

  这两天看到的一个算法题目,恰好我看了第一眼就觉得是求质数,但是,后来总是time out,甚至 error。题目贴出来如下:

Iahub and Iahubina went to a date at a luxury restaurant. Everything went fine until paying for the food.
 Instead of money, the waiter wants Iahub to write a Hungry sequence consisting of n integers.

A sequence a1, a2, ..., an, consisting of n integers, is Hungry if and only if:

1)Its elements are in increasing order. That is an inequality ai < aj holds for any two indices i, j (i < j).
2)For any two indices i and j (i < j), aj must not be divisible by ai. 

Iahub is in trouble, so he asks you for help. Find a Hungry sequence with n elements.

Input

The input contains a single integer: n (1 ≤ n ≤ 10^5).

Output

Output a line that contains n space-separated integers a1 a2, ..., an (1 ≤ ai ≤ 10^7), 
representing a possible Hungry sequence. Note, that each ai must not be greater than 10000000 (10^7) and less than 1.
If there are multiple solutions you can output any one.

Sample test(s)
Input

3

Output

2 9 15

  仔细分析这个题目,其实只是一个小 trick,特别要分析上述题目中给的范围。

(注:第 10000000 个素数是 1299743;Note:101 % 100 != 0)。


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter