2. Prime Generator
Time Limit: 6s Source limit: 50000B
Description
Peter wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers!
Input
The input begins with the number t of test cases in a single line (t<=10). In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space.
Output
For every test case print all prime numbers p such that m <= p <= n, one number per line, test cases separated by an empty line.
Sample Input
5 5 2 1 10 3 5
Sample Output
2 3 5 7 3 5
最近在看一些有限元方面的书,前人所写的程序几乎清一色的都是用Fortran,所以不得不复习一下Fortran了。据说同样的算法用Fortran实现的会比C/C++实现的快25%(当然我没测试过)。不过要找一个支持Fortran的OJ还真是不容易,因为Poj的Fortran编译器不知道出了什么问题,怎么都编译不了,所以只好选择SPOJ了,不过SPOJ支持的语言还真是多,简直可以说是无所不包。
题目的意思还是比较简单的,就是判断素数。这里对筛法做一点变形就可以了。
Fortran太久没写了,或者说以前就掌握了一点皮毛,所以这道题花在调试上的时间比较长。
CODE
function isPrime(n) integer prime(32000) common prime integer n,isPrime isPrime=1 if(n==2) return i=0 do while((prime(i)**2<=n).and.(mod(n,prime(i))/=0)) i=i+1 enddo if(mod(n,prime(i))==0) isPrime=0 end program main integer prime(32000) common prime integer initPrime(32001),t do i=1,32000 initPrime(i)=1 enddo initPrime(2)=1 k=0 do i=2,32000 if(initPrime(i)==1) then prime(k)=i k=k+1 do j=i+i,32000,i initPrime(j)=0 enddo endif enddo read(*,*) t do i=1,t read(*,*) m,n if(m<2) m=2 do j=m,n if(isPrime(j)==1) write(*,"(I0)") j enddo if(i/=t) write(*,*) enddo end
0 条评论。