素生成算法 [英] Prime Generator Algorithm

问题描述

我一直在试图解决素数生成算法的SPOJ问题。

下面是个问题

  

彼得要产生一些质数他的密码。帮帮我   他！你的任务是产生两个之间的所有质数定   数字！

     

输入

     

输入与测试用例数T开头的一行   （T＆LT; = 10）。在每下一吨行有两个数m和n（1   ＆LT; = M＆LT; = N＆LT; = 10亿，N-M＆LT; = 100000），中间用空格隔开

     

输出

     

对于每一个测试用例打印所有素数p，使M＆LT; = P＆LT; = N，   每行一个号码，测试用例由一个空行分隔。

这是很容易的，但网上法官示值误差，我没有什么问题，通过测试案例，为什么这百万范围内需要使用的意思。

下面是我的code。

 ＃包括＆LT; stdio.h中＆GT;

主要（）
{
INT I，NUM1，NUM2，J;
中期息= 0;
scanf函数（％D，和放大器; NUM1，和放大器; NUM2）;
对于（i = NUM​​1; I＆LT; = NUM​​2;我++）
  {
    为（J = 1; J＆LT; = I，J ++）
    {
      如果（我引用％j == 0）
      {
        DIV +;
      }
    }
    如果（格== 2）
    {
     的printf（％D \ N，我）;
    }
    格= 0;
  }
  返回0;
}
 

解决方案

我无法在alogirthm评论和100000号范围是否允许的优化，但你的code是无效的原因是因为它没有似乎是正确分析输入。输入将是这样的：

  2
123123123 123173123
987654321 987653321
 

这是第一行会给组输入的号码，您将与每行，然后是一组输入得到的。您的程序，一目了然，看起来是刚看完第一线找两个数字。

我认为网上法官只是在寻找正确的输出（也可能是合理的运行时间？），所以如果你正确的写输入它应该工作无论什么效率低下是你的算法（如其他人开始评论）

I've been trying to solve the SPOJ problem of Prime number Generator Algorithm.

Here is the question

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.

It is very easy, but the online judge is showing error, I didn't get what the problem meant by 'test cases' and why that 1000000 range is necessary to use.

Here is my code.

#include<stdio.h>

main()
{
int i, num1, num2, j;
int div = 0;
scanf("%d %d", &num1, &num2);
for(i=num1; i<=num2; i++)
  {
    for(j=1; j<=i; j++)
    {
      if(i%j == 0)
      {
        div++;
      }
    }
    if(div == 2)
    {
     printf("%d\n", i);
    }
    div = 0;
  }
  return 0;
}

解决方案

I can't comment on the alogirthm and whether the 100000 number range allows optimisations but the reason that your code is invalid is because it doesn't seem to be parsing the input properly. The input will be something like:

2
123123123 123173123 
987654321 987653321

That is the first line will give the number of sets of input you will get with each line then being a set of inputs. Your program, at a glance, looks like it is just reading the first line looking for two numbers.

I assume the online judge is just looking for the correct output (and possibly reasonable running time?) so if you correct for the write input it should work no matter what inefficiencies are in your algorithm (as others have started commenting on).

这篇关于素生成算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！