陈维晃的个人主页

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