Project1

标题: 蛋疼数学程序帝！质数算法。 [打印本页]
作者: chaochao    时间: 2010-6-27 13:18
标题: 蛋疼数学程序帝！质数算法。
求你认为最好的质数算法。并用程序写出来。
纯属蛋疼。欢迎各位数学帝和程序帝参加……
算法好给奖励哟。
作者: 逸豫    时间: 2010-6-27 13:22
require 'mathn'
prime_number = Prime.new
prime_number.each{|p| puts p ," ";break if p>MAX}
作者: chaochao    时间: 2010-6-27 13:24
对了，为了对得起自己的娘心，大家不要去抄别人的代码，谢谢。
作者: 枫起    时间: 2010-6-27 13:27
表示蛋疼- -。。。。为什么是质数。。。话说人家把质数是什么都忘记了。。。
作者: deleted    时间: 2010-6-27 13:30
提示: 作者被禁止或删除 内容自动屏蔽
作者: DeathKing    时间: 2010-6-27 13:32
嘛……我是来打酱油的。

谬，以前用Ruby搞过，能分解质因数……不过咱俩想到一块儿去了，每周都搞个这个东西{:nm_6:}{:nm_8:}？
作者: 雷欧纳德    时间: 2010-6-27 13:35
啥叫质数我都忘了。。。
作者: IamI    时间: 2010-6-27 13:45
本帖最后由 IamI 于 2010-6-27 14:01 编辑

好吧2L我真的败给你了……常规筛数法，两层循环
  1. prime = (2..1000).to_a
  2. count = 0
  3. begin
  4.   p = prime[count]
  5.   for i in 2..(1000 / p)
  6.     prime.delete i * p
  7.   end
  8.   count += 1
  9. end until count >= prime.size
  10. p prime
复制代码
作者: 亿万星辰    时间: 2010-6-27 13:58
回楼上
prime = (2..1000).to_a
作者: IamI    时间: 2010-6-27 13:59
本帖最后由 IamI 于 2010-6-27 14:01 编辑
回楼上
prime = (2..1000).to_a
亿万星辰 发表于 2010-6-27 13:58

= =b 忘了……但是索引是从1号位置也就是2开始的……我是怎么神奇出来的……
修改完毕
作者: 亿万星辰    时间: 2010-6-27 14:05
本帖最后由 亿万星辰 于 2010-6-27 14:07 编辑

点评系统无法编辑。。。我淡定不能……{:nm_7:}

prime改成从 2 起的话，count还是要修改为0的，否则 4 就无法被剔除~

prime = (2..1000).to_a
count = 0
如此……{:nm_3:}
作者: 蛋糕    时间: 2010-6-27 14:19
本帖最后由 蛋糕 于 2010-6-27 14:21 编辑
  1. 当 要找质数时
  2.    连接网络连接
  3.    百度一下
  4.    将第一个网页输出到输出框
  5. 结束
复制代码
好罢……写完这个以后我真的蛋糕疼了……
作者: 枫起    时间: 2010-6-27 14:23
表示我的最简单
http://baike.baidu.com/view/2868105.htm
作者: 紫苏    时间: 2010-6-27 14:32
比较简单的是埃拉托斯特尼筛法：

BOUND = 1000000
primes = new bits[BOUND+1]
memset(primes, 1)
for i from 2 to BOUND
    if primes[i] then
        println(i)                // 输出质数
        j = i << 1
        while j < BOUND
            primes[j] = 0
            j += i
        end while
    end if
end for

还有一个阿特金筛法，据说是上述筛法的优化版，但没有试过
以上是找出某范围内所有质数的算法，但如果只是要确定某个数是不是质数的话，那直接用数学方法里的素性测试就行了
作者: 上帝的眼睛    时间: 2010-6-27 14:32
本帖最后由 上帝的眼睛 于 2010-6-27 14:40 编辑
  1. MAX = 100
  2. prime = []
  3. for i in 0..MAX-2
  4. prime[i] = i+2
  5. end
  6. i = 0
  7. j = 2
  8. while prime[i] != nil
  9.   while prime[i]*j < MAX
  10.     prime.delete(prime[i]*j)
  11.     j += 1
  12.   end
  13.   i += 1
  14.   j = 2
  15. end
  16. p prime
复制代码
好吧……这个是我自己写的……效率什么的无视就好……
看着这里的一对狂人们讨论，我真的好羡慕……
作者: 紫苏    时间: 2010-6-27 14:43
II 和上帝的眼睛都用了动态数组的 delete，无形中就丢失效率了

另外还有个不是特别重要的问题：乘法运算需要多次移位，理论上来说是比加法要慢的，上面的乘法都可以由加法替换
1 * n = n
2 * n = n + n
....
作者: IamI    时间: 2010-6-27 14:46
本帖最后由 IamI 于 2010-6-27 14:50 编辑
II 和上帝的眼睛都用了动态数组的 delete，无形中就丢失效率了

另外还有个不是特别重要的问题：乘法运算需 ...
紫苏 发表于 2010-6-27 14:43

那么用数组标记法……输出的时候再全扫描一次？
另外2的次方也可以邪恶一下……

好吧……我没看见前面的东西……去研究下
作者: 紫苏    时间: 2010-6-27 14:58
那么用数组标记法……输出的时候再全扫描一次？
另外2的次方也可以邪恶一下…… ...
IamI 发表于 2010-6-27 14:46

嗯，你俩写的本质上其实都是埃拉托斯特尼筛法，只不过你们用的是元素来存数值，而我用的是用第 n 位来表示 n 是否为质数。C++ STL 里有一个现成的容器类 bitset，可以当做位数组来用

另外上帝的眼睛给的链接里的算法还是没有脱离埃拉托斯特尼筛法的思想，刚搜了一下阿特金筛法，应该能比这个更快些：http://en.wikipedia.org/wiki/Sieve_of_Atkin
作者: 上帝的眼睛    时间: 2010-6-27 15:06
本帖最后由 上帝的眼睛 于 2010-6-27 15:15 编辑
  1. MAX = 10000
  2. t1 = Time.now
  3. prime = []
  4. kick = []
  5. for i in 0..MAX-2
  6. prime[i] = i+2
  7. kick[i] = false
  8. end
  9. i = 0
  10. j = 2
  11. while prime[i] != nil
  12.   while prime[i]*j < MAX
  13.     #prime.delete(prime[i]*j)
  14.     kick[prime[i]*j-2] = true
  15.     j += 1
  16.   end
  17.   i += 1
  18.   j = 2
  19. end
  20. prime.each{|v| puts v unless kick[v-2]}
  21. t2 = Time.now
  22. p t2-t1
复制代码
果然，这样很能提升效率么……（忽视最后一个……）

忽然想起来我买的一本书 《素数的音乐》……
作者: 紫苏    时间: 2010-6-27 15:40
本帖最后由 紫苏 于 2010-6-27 15:41 编辑

回复 上帝的眼睛 的帖子

这个其实自己做个测试也就知道了：
  1. CASES = 5000

  3. arr1 = (0...CASES).to_a
  4. arr2 = (0...CASES).to_a

  6. t = Time.now
  7. CASES.times { |i| arr1.delete(i) }
  8. p Time.now - t


  11. t = Time.now
  12. CASES.times { |i| arr2[i] }
  13. p Time.now - t
复制代码
同样长度的数据，删除花的时间比随机访问多得多，从实现的角度来想，如果动态数组是乱序线性结构的话，那么删除元素就有一个线性搜索的过程，搜索到了该元素，还要让后面的元素前移， realloc 下内存大小；访问则是简单的数组首地址 + 偏移量
所以如果想要效率的话，删除元素必须慎用，除非你用的是散列表或是自我平衡/B/B+树之类的可以高效插入/删除的结构

另外附一个乘法和加法时间的比较：
  1. CASES = 10000000

  3. t = Time.now
  4. for i in 1..CASES
  5.   i + i
  6. end
  7. p Time.now - t

  9. t = Time.now
  10. for i in 1..CASES
  11.   i * 2
  12. end
  13. p Time.now - t
复制代码
作者: 亿万星辰    时间: 2010-6-27 15:57
其实从来就不懂效率这东西的人飘过了……{:nm_8:}
作者: chaochao    时间: 2010-6-27 17:34
  1.     public class suanfa1
  2.     {
  3.         private DateTime startDateTime;
  4.         public DateTime StartDateTime
  5.         {
  6.             get { return startDateTime; }
  7.             set { startDateTime = value; }
  8.         }
  9.         private DateTime endDateTime;
  10.         public DateTime EndDateTime
  11.         {
  12.             get { return endDateTime; }
  13.             set { endDateTime = value; }
  14.         }
  15.         private List<ulong> number;
  16.         public List<ulong> Number
  17.         {
  18.             get { return number; }
  19.             set { number = value; }
  20.         }
  21.         public void getzhishu(ulong max)
  22.         {
  23.             number = new List<ulong>();
  24.             number.Add(2);
  25.             number.Add(3);
  26.             for (ulong i = 3; i < max; i+=2)
  27.             {
  28.                 if (iszhishu(i, number))
  29.                 {
  30.                     number.Add(i);
  31.                 }
  32.             }
  33.         }
  34.         private bool iszhishu(ulong i, List<ulong> number)
  35.         {
  36.             ulong hi=i/2;
  37.             ulong num = 0;
  38.             for (int j = 0; j < number.Count; j++)
  39.             {
  40.                 num = number[j];
  41.                 if (num > hi) return true;
  42.                 if (i % num == 0)
  43.                 {
  44.                     return false;
  45.                 }
  46.             }
  47.             return true;
  48.         }
  49.         //程序入口
  50.         public static void Main(string[] args)
  51.         {
  52.             ulong max = 100000;
  53.             suanfa1 sf1 = new suanfa1();
  54.             sf1.StartDateTime = DateTime.Now;
  55.             sf1.getzhishu(max);
  56.             sf1.EndDateTime = DateTime.Now;
  57.             int count = sf1.Number.Count;
  58.             StringBuilder sb = new StringBuilder();
  59.             for (int i = 0; i < count; i++)
  60.             {
  61.                 sb.AppendLine("" + sf1.Number[i]);
  62.             }
  63.             System.Console.Out.Write(sb.ToString());
  64.             System.Console.Out.WriteLine("");
  65.             System.Console.Out.WriteLine("用时:" + ((sf1.EndDateTime.Ticks - sf1.StartDateTime.Ticks) / 10000) + "毫秒");
  66.         }
  67.     }
复制代码
以上代码100000以内0.7秒左右，1000000以内大约40秒……嘛嘛……什么时间的无视好了，反正速度和机器好坏有关。
第一层循环的方法还可以继续优化，通过更快的算法可以找出有质数嫌疑的数字然后再去判断，这样计算效率会更高，明天再来研究看看吧，一天都没睡觉了，现在头昏脑胀的……
作者: 雷欧纳德    时间: 2010-6-27 17:53
其实查表法才是最快的～～～
作者: bzzdhm    时间: 2010-6-27 18:06
百度一下，你就知道
作者: 模仿者    时间: 2010-6-27 18:06
回复 chaochao 的帖子


    java的 {:nm_6:} 貌似java的效率本身就比C要低些
作者: bzzdhm    时间: 2010-6-27 18:08
制作格斗游戏用拳头效率最高
作者: 模仿者    时间: 2010-6-27 18:09
回复 bzzdhm 的帖子

说起格斗游戏 KOF是神作
   
作者: bzzdhm    时间: 2010-6-27 18:13
反正我不玩格斗游戏……
我们这学校最流行的格斗游戏就是后操场
作者: 南瓜头    时间: 2010-6-27 18:15
嗯  我还记得那次和豌豆射手玩真实格斗游戏的说
结果我都不能攻击 就那样被KO了 TAT
作者: 模仿者    时间: 2010-6-27 18:19
回复 南瓜头 的帖子


    你可以和睡莲或者花盆玩嘛，坚果墙也行{:nm_6:}
作者: 南瓜头    时间: 2010-6-27 18:26
回复 模仿者 的帖子


    和睡莲一起玩 等她长大了就不能和她一起玩了 长大了就带刺了
作者: 玮哥投胎了    时间: 2010-6-27 22:38
26的开始走题……

对我而言，简直就是在看一群神在写天书
作者: 紫苏    时间: 2010-6-28 02:43
回复


    java的  貌似java的效率本身就比C要低些
模仿者 发表于 2010-6-27 18:06


chaochao 的代码是 C#，Java 没有 ulong 这种无符号类型，也没有 List<?>
其实看到 System.Console 就基本上就可以肯定是 C# 了……

chaochao 那个是用可能的质因数试除来判断素性，那内层循环里可以加一个 num <= sqrt(i)

说到平方根，发现我之前写的也没考虑平方根方面的优化，特此补上：

  2. BOUND = 1000000
  3. primes = new bits[BOUND+1]
  4. memset(primes, 1)
  5. for i from 2 to BOUND
  6.     if primes[i] then
  7.         println(i)                // 输出质数
  8.         j = i * i
  9.         while j <= BOUND
  10.             primes[j] = 0
  11.             j += i
  12.         end while
  13.     end if
  14. end for
复制代码
之前写的 j 是从 i << 1 开始，但 i 的小于 i^2 的倍数肯定是已经被之前的质数筛掉了的，所以应该从 i^2 开始
在我的机器上用 VC++ 编译器编译的程序测试，100万以内瞬间算完，1000万低于1秒
如果没弄错的话，埃拉托斯特尼筛法需要 O(n log log n) 时间
作者: yangff    时间: 2010-6-28 08:37
筛子大发
设数组A={true,false,...,false}(1~n)
找到质数A中第一个false的位置(k)
则输出，标记为true，然后把i*k (i*k<=n)全部置true
重复直到数组A为空
作者: Itol    时间: 2010-6-28 09:43
提示: 作者被禁止或删除 内容自动屏蔽
作者: 雷欧纳德    时间: 2010-6-28 10:24
程序帝来了，传说中的查表法，保证比ls那些速度快-v-|||
  1.                 int temp[] = {
  2.                 2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
  3.                 31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
  4.                 73, 79, 83, 89, 97, 101, 103, 107, 109, 113,
  5.                 127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
  6.                 179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
  7.                 233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
  8.                 283, 293, 307, 311, 313, 317, 331, 337, 347, 349,
  9.                 353, 359, 367, 373, 379, 383, 389, 397, 401, 409,
  10.                 419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
  11.                 467, 479, 487, 491, 499, 503, 509, 521, 523, 541,
  12.                 547, 557, 563, 569, 571, 577, 587, 593, 599, 601,
  13.                 607, 613, 617, 619, 631, 641, 643, 647, 653, 659,
  14.                 661, 673, 677, 683, 691, 701, 709, 719, 727, 733,
  15.                 739, 743, 751, 757, 761, 769, 773, 787, 797, 809,
  16.                 811, 821, 823, 827, 829, 839, 853, 857, 859, 863,
  17.                 877, 881, 883, 887, 907, 911, 919, 929, 937, 941,
  18.                 947, 953, 967, 971, 977, 983, 991, 997,};
  19.                 for (int i=0; i<168; i++)
  20.                 {
  21.                                 std::cout << temp[i] << std::endl;
  22.                 }
复制代码
作者: 模仿者    时间: 2010-6-28 10:54
回复 雷欧纳德 的帖子


    请用此方法列出1亿以内的{:nm_6:}
作者: 雷欧纳德    时间: 2010-6-28 10:55
回复 模仿者 的帖子


我先用ls的方法算出1亿以内的表并生成代码就行了，然后我还是最快的
作者: 赤点    时间: 2010-6-28 14:09
其实查表法才是最快的～～～
雷欧纳德 发表于 2010-6-27 17:53



+1
作者: kaze    时间: 2010-6-28 14:22
DES里面要生成的素数都是大于long的,乃们这么闲就去研究32位素数吧= =
作者: 紫苏    时间: 2010-6-28 15:05
DES里面要生成的素数都是大于long的,乃们这么闲就去研究32位素数吧= =
kaze 发表于 2010-6-28 14:22


要找超大质数的话通常就不会用上面这种列出所有质数的算法了，目前研究员们找最大质数的方式是先找出有可能是质数的梅森数，然后用卢卡斯莱默检验法来检测素性，并未费神去找一个不是梅森数的质数

另外 DES 好像是针对对称加密吧，需要超大质数的是非对称加密算法，如 RSA
作者: 浩气青天    时间: 2010-6-28 18:53
都是一群数学帝程序帝啊！
数学几乎盲的路过。。。。
作者: 菜鸟飞呀飞    时间: 2010-8-28 04:04
提示: 作者被禁止或删除 内容自动屏蔽



欢迎光临 Project1 (https://rpg.blue/) Powered by Discuz! X3.1