Abordagem interessante. Eu já tinha feito algo em C da seguinte forma:
/*
Autor: Dante Cardoso Pinto de Almeida
Licenca: Dominio Publico - Public Domain
*/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
int main(int argc, char *argv[])
{
int rodando;
rodando=1;
while(rodando==1)/*Este laco mantem o programa rodando enquanto o usuario desejar*/
{
unsigned long int m, n, x, y, z, divisores, resto, loop, ver;
int time1, time2;
n=0;
m=0;
loop=0;
while(n<2) /*Este laco impede a entrada de numeros menores que dois*/
{
printf("Entre com um numero inteiro maior ou igual a 2: ");
scanf("%d", &n);
}
while(m<=n) /*Este laco impede a entrada de numeros menores que n*/
{
printf("Entre com um outro numero inteiro, maior que %d: ", n);
scanf("%d", &m);
}
printf("Existem os seguintes primos no intervalo entre %d e %d:\n\n", n, m);
time1 = clock(); /*Comeco da contagem do tempo de execucao*/
for(x=n; x!=m; x++) /*Este laco varre todos os numeros do intervalo*/
{
divisores=0;
y=x;
ver=1;
if((x%2==0 && x!=2)||(x%3==0 && x!=3)||(x%5==0 && x!=5)||(x%7==0 && x!=7)||(x%11==0 && x!=11)||(x%13==0 && x!=13)||(x%17==0 && x!=17)||(x%19==0 && x!=19)||(x%23==0 && x!=23)||(x%29==0 && x!=29))
{
ver=0;
}
/*Estas duas condições fazem o programar pular os multiplos de 2, 3, 5, 7, 11, 13, 17, 19, 23 e 29*/
if(ver==1)
{
while(divisores<2) /*Este laco faz parar o teste de um numero assim que se verificar mais de dois divisores*/
{
while(y!=0) /*Este laço faz um numero ser dividido por todos seus antecessores*/
{
resto = x%y;
if(resto==0)
{
divisores++; /*conta a quantidade de divisores*/
}
if(y==x)/*Esta condicao acelera a execucao do programa fazendo o teste da divisibilidade pular logo para metade do numero*/
{
y=y/2;
}else{
y=y-1;}
}
}
}
if (divisores==2) /*Esta condicao imprime todos os numeros verificados como primos*/
{
printf("%8ld", x);
loop++; /*Contagem da quantidade de primos no intervalo*/
}
}
printf("\nO que totaliza %d numeros primos dentro do intervalo.\n", loop);
time2 = clock();
printf("Levou %d unidades de tempo para executar o teste.",time2-time1);
printf("\nDigite 1 para continuar rodando o programa.");
printf("\nDigite qualquer outro numero para encerrar o programa.\n");
scanf("%d", &rodando);
}
return 0;
}