质数判断程序(仅限4位数)

小叽

纯RUBY下写的素数检验小程序!  经过验证对十万亿位(14位)以内的数皆可(其实对14位以上的数都可以算,只是时间超长,都可以长出蜘蛛网来饿).

1. t1 = Time.now  #=====获取开始时间
   
2. m =  23333333335313    #=====需要计算的数
   
3. x= 0
   
4. if m == 2
   
5.   print "2是一个素数\n一共经过了0次计算\n"
   
6.   else
   
7. for a in 2..(Math.sqrt(m)+1)
   
8. if a >3 and (a%2 == 0 or a%3 == 0 or a%5 == 0  or a%7 == 0 or a%11 == 0 or a%13 == 0 )
   
9.   next
   
10. end
    
11. b = m/a
    
12.      x += 1
    
13.      if a*b != m   
    
14.          next
    
15.         else
    
16.           f = true
    
17.          print m,"=",a,"*",b,"     ",   m,"不是一个素数\n"
    
18.          break
    
19.        end
    
20. end
    
21. if f == nil
    
22.    print m,"是一个素数\n"
    
23. end
    
24.   print  "一共经过了",x,"次计算\n"
    
25. end
    
26.   t2 = Time.now     #======获取结束时间
    
27. print t2-t1,"sec\n"#======得到计算时间

复制代码

十万亿的计算须时甚长! 一般的万亿位内都比较快(不超过数秒)!
>ruby 验证素数.rb
23333333335313是一个素数
一共经过了926522次计算
22.547sec
>Exit code: 0

小叽

囧，其实我们可以把发现的所有质数列个数组，然后比较 囧
orochi2k 发表于 2009-7-25 22:48

有什么囧的,美国的那个素数检验计算机就是这样做的.让一个未知的数去除数据库里已知的素数,不被整除则为素数.!如此循环往下.

orochi2k

其实RUBY根本不适合干这事，还是用汇编吧  囧
理由：
1，程序不长
2，开发效率没要求
3，执行效率要求很高

DeathKing

说…………RGSS算质数不如VB或VC吧？

mafiaboy

PY版的（跟ruby好像）
h = 0
leap = 1
from math import sqrt
from sys import stdout
for m in range(1,20000):
    k = int(sqrt(m + 1))
    for i in range(2,k + 1):
        if m % i == 0:
            leap = 0
            break
    if leap == 1:
        print '%-4d' % m
        h += 1
        if h % 10 == 0:
            print ''
    leap = 1
print 'The total is %d' % h

mafiaboy

说…………RGSS算质数不如VB或VC吧？
DeathKing 发表于 2009-7-27 19:12

恩 这一个是最快的求100以内质数方法（转载）
DSEG SEGMENT
count dw 0;存放素数的个数
sum dw 0;存放素数的和
sushu db 100 dup(?);存放素数
msgsushu db 'all of sushu are:','$';显示素数的提示信息
msgcount db 0dh,0ah,'count of sushu is:',0dh,0ah,'$';显示素数个数的提示信息
msgsum db 0dh,0ah,'sum of sushu is:',0dh,0ah,'$';显示素数和的提示信息
DSEG ENDS

CSEG SEGMENT
assume cs:CSEG, ds:DSEG

MAIN PROC FAR ;主程序入口
call jisuan;将100以内素数的个数存入COUNT单元中，素数的和存入SUM单元中，并将素数存入内存自SUSHU开始的单元中

lea dx,msgsushu;显示素数的提示信息
mov ah,9
int 21h
call dispsushu;显示素数

lea dx,msgcount;显示素数个数的提示信息
mov ah,9
int 21h
call dispcount;显示素数个数

lea dx,msgsum;显示素数和的提示信息
mov ah,9
int 21h
call dispsum;显示素数和

mov ah,1;按任意键退出
int 21h
mov ax, 4c00h ;程序结束，返回到操作系统系统
int 21h
MAIN ENDP

jisuan proc near
mov ax, dseg
mov ds, ax
lea di,sushu
mov bh,0
mov bl,2;求从2到100的素数、素数个数、素数的和，BL从2到100变化
next11:
cmp bl,100
ja tj
mov dl,2;如果BL不能被DL从2到BL-1整除的话，则BL为素数
next12:
cmp dl,bl
jae next13
mov ax,bx
div dl
cmp ah,0
jz next14;整除则不是素数
inc dl
jmp next12
next13:
inc count;是素数，则将个数加1
add sum,bx;是素数,则加到和中
mov [di],bl;是素数，则存入相应单元中
inc di
next14:
inc bl
jmp next11
tj:ret
jisuan endp

dispsushu proc near
lea si,sushu
mov cx,count
next21:
mov ax,count;每行10个素数
sub ax,cx
mov bl,10
div bl
cmp ah,0
jnz next22
mov dl,0dh;每行10个素数，行末加回车换行
mov ah,2
int 21h
mov dl,0ah
mov ah,2
int 21h
next22:
mov bl,[si];取出一个素数
mov bh,0
call disp10;以十进制形式输出
mov dl,20h;每个素数之间加一个空格，便于区分
mov ah,2
int 21h
call delay;每输出一个素数都有数秒的停顿，延时子程序
inc si
loop next21
ret
dispsushu endp

dispcount proc near
mov bx,count;取出素数个数
call disp10;以十进制形式输出
ret
dispcount endp

dispsum proc near
mov bx,sum;取出素数的和
call disp10;以十进制形式输出
ret
dispsum endp

disp10 proc near;该子程序的作用是将BX中的数以十进制形式输出
push cx
mov cx,1000d
call dec_div
mov cx,100d
call dec_div
mov cx,10d
call dec_div
mov cx,1d
call dec_div
pop cx
ret
dec_div proc near
mov ax,bx
mov dx,0
div cx
mov bx,dx
mov dl,al
add dl,30h
mov ah,2
int 21h
ret
dec_div endp
disp10 endp

delay proc near;该子程序的功能是延时
push cx
push ax
mov ax,60000
nextd1:
mov cx,6000
nextd2:
loop nextd2
dec ax
jnz nextd1
pop ax
pop cx
ret
delay endp

CSEG ENDS
END MAIN

小叽

:dizzy:汇编???????????