质数求法及 a trick

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

  一般求质数方法就是判断数 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)。

Avatar_small
Emma 说:
2022年12月29日 19:53

Prime numbers are whole numbers that can only be divided evenly by 1 or themselves. They are very important in math and science, and there are a few different ways to find them. One way to find prime numbers is Lab grown diamonds to use a factor tree. This is a tree-like diagram that starts with the number you are trying to find the factors of at the top, and then breaks the number down into smaller factors until you are left with only prime numbers. Another way to find prime numbers is to use a sieve. This is a process of crossing out numbers on a list that are not prime, and the numbers that are left are the prime numbers.


登录 *


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