`
RednaxelaFX
  • 浏览: 3053200 次
  • 性别: Icon_minigender_1
  • 来自: 海外
社区版块
存档分类
最新评论

算区间内质数。好慢啊 T T

    博客分类:
  • F#
阅读更多
读了night_stalker老兄的Ruby算法求优化:spoj PRIME1,深感自己对Ruby的性能特性了解的太少了。也试了些办法不过最多也就得到了10%左右的性能提升,没啥意义。

想想,干脆用F#来试试看。这个是F# 1.9.6.2,运行环境是HP nx9040/Windows 7 Beta Build 7000。随手写了一份代码,先通过记录已知的非质数得到sqrt(n)以内的质数表ps,然后用筛选法求m..n之间的质数:
#light

let primesBetween m n =
  let pmax = int << sqrt << float <| n
  let rec loop i ps kn =
    if i > pmax then ps
    else
      let kn_next = List.fold_left (fun (acc : int Set) e -> acc.Add(e)) kn [i..i..pmax]
      loop (i + 2) (if kn.Contains(i) then ps else i :: ps) kn_next
  let ps = loop 3 [2] (Set [])
  let mm = if m <= 2 then 3 else if m % 2 = 0 then m + 1 else m
  let cand1 = List.init ((n - mm >>> 1) + 1) (fun i -> (i <<< 1) + mm)
  let cand2 = cand1 |> List.filter (fun e ->
    None = List.tryfind (fun p -> e % p = 0 && e <> p) ps)
  if m <= 2 then 2 :: cand2 else cand2

open System.Diagnostics
let watch = new Stopwatch()
watch.Start()
let primes = primesBetween 999900000 1000000000
watch.Stop()
printfn "%A" primes
printfn "%A" watch.ElapsedMilliseconds

在我的机器上运行,速度居然跟Ruby 1.9.1差不多 OTL
引用
5425L

把第8行的List.fold_left和[i..i..pmax]换成对应的Seq版,Seq.fold和{i..i..pmax},速度只有很细微的提升。瓶颈是出在什么地方我也没弄清楚。

呜,太慢了。不过慢的主要原因应该还是我写的太糟糕了。
这种事情还是应该开多线程并行计算的好。改用比较原始的筛选法就有机会并行。以后有空再玩玩 T T
分享到:
评论

相关推荐

    算法-区间内的真素数(信息学奥赛一本通-T1411).rar

    标题中的“算法-区间内的真素数”是一个与数学和计算机科学相关的话题,特别是对于信息学奥赛的参赛者来说,这是一个重要的知识点。在信息学竞赛中,算法的设计和实现能力是关键,而素数相关的算法是常考的题目类型...

    整数区间(信息学奥赛一本通-T1324).rar

    例如,找到区间[1, n]内最大的质数。 5. 区间计数:统计区间内满足某个条件的整数个数。例如,计算区间[1, n]内偶数的个数。 解决这些问题,通常需要用到的数据结构有区间树、线段树、平衡二叉搜索树等。区间树和...

    判断素数题目,分函数;

    - **输出格式**:对于每个给定的区间,如果该区间内所有表达式的值都为素数,则输出"OK";否则输出"Sorry"。每组结果占一行。 - **示例**: - 输入样例: ``` 0 1 0 0 ``` - 输出样例: ``` OK ``` #### ...

    随机生成两个2~100之间的随机数a和b,找出区间a,b (a<b)内的素数,并用列表保存,输出前5个素数和该5个素数的均值

    用来随机生成两个2~100之间的随机数a和b,找出区间[a,b] (a)内的素数,并用列表保存,输出前5个素数和该5个素数的均值,保留两位小数。如果该区间内不足5个素数,重新生成区间并重复以上过程。以

    c#求范围内素数的示例分享(c#求素数)

    程序分析:判断素数的方法:用一个数分别去除2到sqrt(这个数),如果能被整除,则表明此数不是素数,反之是素数。 代码如下:#include &lt;stdio&gt;#include &lt;math.h&gt; void main(){ int low,high,t=0; printf(“请...

    连号区间数.zip

    标题中的“连号区间数”很可能是指一个编程竞赛或练习题目,这通常涉及到寻找一系列数字中的连续子序列或连续区间。在程序设计和算法领域,这类问题常常要求编写高效的算法来解决,例如寻找数组中最大长度的连续子...

    算法-判断整除(信息学奥赛一本通-T1195)(包含源程序).rar

    5. **区间整除**:在一定范围内找出所有能被特定数整除的数。 编写源程序时,可以使用循环、条件判断、函数等编程结构来实现这些操作。例如,使用for循环遍历一个范围内的数,然后用if语句判断每个数是否满足整除...

    计算机等级考试2级机试题c语言

    函数 `void fun(int m, int k, int xx[])` 的任务是在 `[m, m*m]` 区间内寻找前 `k` 个素数,并将它们存入 `xx` 数组中。 **关键代码分析:** ```c void fun(int m, int k, int xx[]){ int g = 0, i, j, flag = 1;...

    PTA实验LB05-LB08.pdf

    在这个实验中,我们需要编写一个程序来统计在给定的整数M和N区间内的素数个数,并计算它们的和。素数是大于1且只有1和自身两个正因数的自然数。在示例代码中,`isPrime`函数用于判断一个数是否为素数。它通过检查从...

    2023级cpp上机练习题第13次(有返回值函数)

    2. **统计计数器**: 变量`t`用于统计区间内完美平方数的数量。 ### 知识点四:判断数字是否被3、5或7整除 #### 示例4: 判断是否能被3、5或7整除 ```cpp bool f(int m){ if (m%3==0||m%5==0||m%7==0){ return ...

    西工大c语言100道题

    程序首先输入方程的两个根的初始区间,然后不断缩小区间,直到找到满足方程的根,满足的条件是连续两次区间内的中点使得方程的符号改变。 5. CH0615:这道题是找出所有可能的三个不重复的大写字母组合。使用三层...

    西工大poj2014

    5. **T1204(判断是否为素数)**:这是一个基础的数论问题,需要实现一个函数来检查一个数是否为素数,可能使用试除法或者更高效的筛法(如埃拉托斯特尼筛法)。 6. **T031(最大整数)**:题目可能要求找出一组整数...

    论文研究-配分函数法的改进及应用.pdf

    针对传统配分函数难以处理分割子区间长度s不为时间序列长度T的约数或者T为质数的情况,采用类似多重分形去趋势波动法(MFDFA)的操作方式,提出修正配分函数法....

    NOIP模拟试题

    - 性质二:反素数的形式可以写作\(p = 2^{t_1} * 3^{t_2} * 5^{t_3} * 7^{t_4} \cdots\),并且有\(t_1 \geq t_2 \geq t_3 \geq \cdots\)。这个性质允许我们使用深度优先搜索或广度优先搜索来枚举可能的反素数。 - ...

    c++期末例题111111111

    2. 求一个区间为[0,1000)内的整数的各位上的数字和 数字处理 这道题目要求计算一个整数的各位数字之和。代码使用了除法和模运算来计算各位数字,并将其相加。 代码实现: ```cpp int main(){ int n; int a,b,c;...

    PYTHON知识点汇总 图文.docx

    - 题目21中,出租车费用的计算涉及到分段函数,需要根据行驶的公里数`s`判断处于哪个区间,并根据区间内的费用规则进行计算。 6. **算法分析**: - 题目21的算法采用了解析法,通过分段函数解析计算费用。 - ...

    C语言常用算法集合

    梯形法的基本思想是将被积函数分成多个小区间,在每个小区间内用梯形面积来近似该区间的积分值。 ```c double integral(double a, double b, long n) { long i; double s, h, x; h = (b - a) / n; s = h * (f(a)...

    BessDerivZerosBisec​t:计算 J_m 素数的零点-matlab开发

    计算前 m 个函数 J'm 的前 k 个零的表。 这里Jm是整数阶m的第一类Bessel函数,而J'm是其导数。 这些函数出现在许多涉及圆柱几何的问题中。 使用了一个简单的二分算法,因为它允许构造区间来支撑每个连续的根。

    C程序设计算法归纳

    牛顿迭代法和二分法分别用于寻找给定区间内的方程根,牛顿迭代法通过迭代公式不断逼近根,而二分法则不断缩小区间直至满足精度要求。 12. **弦截法求根**: 弦截法是介于牛顿迭代法和二分法之间的一种方法,它...

Global site tag (gtag.js) - Google Analytics