几个有意思的问题_第二弹

熊猫

我熊猫又回来啦
同时我也带来了我的最新的Prime计算代码：

1.     Public Function Check_Prime(ByVal Num As Integer) As Boolean
   
2.         Try
   
3.             If Num = 1 Or Num = 2 Then Return True : Exit Function
   
4.             Dim DefinedPrime As Integer = 0
   
5.             Dim StartNum As Integer = 2
   
6.             Dim NumSqr As Integer = Math.Sqrt(Num)
   
7.             If PrimeSet.Count <> 0 Then
   
8.                 If PrimeSet.Item(UBound(PrimeSet.ToArray)) > NumSqr Then
   
9.                     For S As Integer = PrimeSet.Count - 1 To 0 Step -1
   
10.                         DDNum += 1 '迭代计数器+1
    
11.                         If PrimeSet(S) < NumSqr Then
    
12.                             DefinedPrime = S
    
13.                         Else
    
14.                             Exit For
    
15. 
    
16.                             'StartNum = PrimeSet(S) + 1
    
17.                         End If
    
18.                     Next
    
19.                     For S As Integer = 1 To DefinedPrime
    
20.                         DDNum += 1 '迭代计数器+1
    
21.                         If Num Mod PrimeSet(DefinedPrime - 1) = 0 Then
    
22.                             Return False
    
23.                             Exit Function
    
24.                         End If
    
25.                     Next
    
26.                 End If
    
27.             End If
    
28.             For S As Long = StartNum To Math.Sqrt(Num)
    
29.                 DDNum += 1 '迭代计数器+1
    
30.                 If Num Mod S = 0 Then Return False : Exit Function
    
31.             Next
    
32.             Call Add_Prime(Num)
    
33.             Return True
    
34.         Catch ex As Exception
    
35.             MessageBox.Show(ex.Message)
    
36. 
    
37.         End Try
    
38. 
    
39.     End Function

复制代码

比起上一个版本，反向了一个循环，计算1000以内的Prime，迭代次数仅有6367次！少了一倍多。

苏小脉

回复 熊猫 的帖子

熊猫可以试试 Eratosthenes 筛法，构建 1000 内质数表只需要 917 次迭代。Atkin 筛法更优呢。

1. 
   
2. BOUND = 1000
   
3. primes = [ false, true ] * ((BOUND + 1) >> 1)
   
4. primes[2] = true
   
5. 
   
6. i = 3
   
7. count = 0
   
8. while i * i <= BOUND
   
9.     if primes[i] then
   
10.         j = i * i
    
11.         while j <= BOUND
    
12.             primes[j] = false
    
13.             j += i
    
14.             
    
15.             count += 1
    
16.             
    
17.         end
    
18. 
    
19.     else count += 1
    
20. 
    
21.     end
    
22.     i += 2
    
23. end
    
24. 
    
25. p count # 917
    

复制代码

熊猫

回复 苏小脉 的帖子

1. BOUND = 1000
   
2. primes = [ false, true ] * ((BOUND + 1) >> 1)
   
3. primes[2] = true
   
4. 
   
5. i = 3
   
6. count = 0
   
7. while i * i <= BOUND
   
8.     if primes[i] then
   
9.         j = i * i
   
10.         while j <= BOUND
    
11.             primes[j] = false
    
12.             j += i
    
13.             
    
14.             count += 1
    
15.             
    
16.         end
    
17. 
    
18.     else count += 1
    
19. 
    
20.     end
    
21.     i += 2
    
22. end
    
23. for s in 1..10
    
24.   p s.to_s + "  " +primes[i].to_s
    
25. end
    
26. p count

复制代码

我怎么感觉这个筛选得不对呢？我提取了10个结果。。都是false啊。。

苏小脉

熊猫 发表于 2011-4-10 14:58
回复 苏小脉 的帖子

我怎么感觉这个筛选得不对呢？我提取了10个结果。。都是false啊。。 ...

最后那里 primes 的下标写成 i 了。。。

熊猫

回复 苏小脉 的帖子

1. #include <stdio.h>
   
2. #include <math.h>
   
3. int main()
   
4. {
   
5.   int number;
   
6.   int i;
   
7.   int square;
   
8.   int n;
   
9.   int time=0;
   
10.   scanf("%d",&number);
    
11.   int num[number];
    
12.   for (i=0;i<number;i++)
    
13.   {
    
14.     num[i]=i+1;
    
15.   }
    
16.   square = (int)(pow(number,0.5));
    
17.   i = 0;
    
18.   while (i<number)
    
19.   {
    
20.     if (num[i] % 2 == 0)
    
21.     {
    
22.       num[i] = 0;
    
23.     }
    
24.     i++;
    
25.   }
    
26.   for (n=3;n<=square;n=n+2)
    
27.   {
    
28.     i = n;
    
29.     n = pow(n,2);
    
30.     while (n < number)
    
31.     {
    
32.       num[n-1]=0;
    
33.       n=n+2*i;
    
34.       time+=1;
    
35.     }
    
36.     if (n>=number)
    
37.     {
    
38.       time+=1;
    
39.     }
    
40.     n = i;
    
41.     }
    
42.     printf("prime number 2\n");
    
43.   for (i=0;i<number;i++)
    
44.   {
    
45.     if ((num[i]==0)||(num[i]==1))
    
46.     {
    
47.     }
    
48.     else
    
49.     {
    
50.       printf("prime number %d\n",num[i]);
    
51.     }
    
52.   }
    
53.   printf("iterated %d times\n",time);
    
54. 
    
55. 
    
56. 
    
57. 
    
58. return 0;
    
59. }

复制代码

嗯…………最终发布-Ultimate代码
迭代578次。。。远小于16000、12000、6000、5000、900……
某普渡大学在校学生供稿。。
QQ：249834305


为什么会比900那个少？是因为n=n+2*i;取代了原来那个代码的j += i。
如果直接加的话，奇数+奇数=偶数，所以这样没有必要判断，加n的2倍，奇数+偶数=奇数。这就少了400次迭代。

苏小脉

熊猫 发表于 2011-4-10 17:53
回复 苏小脉 的帖子

嗯…………最终发布-Ultimate代码

有意思！奇数相加那个真没想到 XD
不过这个版本的内层 while 循环外面没加上是否是质数的判断——只有质数的倍数需要被筛掉。
另外内层 while 下面那个 time += 1 会产生重复的计数（在进入了 while 的场合下）。

和我之前那个互补之后，迭代减少到了 462。

苏小脉

evolniar 发表于 2011-4-11 03:00
回复 苏小脉 的帖子

需要的，因为每一次判断都得算作一次迭代，所以不管通不通过while，都要算一次。 ...

先生所谓“每一次判断”为何？
学生且将“不管通不通过while，都要算一次”理解为“通过 while 则一次以上，不通过则一次”之意，然二十五楼代码却是“通过 while 则两次以上，不通过则一次”。

学生以为理当如此：

1. 
   
2. if (B) { while (B) { ... ++times; ... } } else { ... ++times; ... }

复制代码