打印出小于给定数字的素数N

打印出小于给定数字N的素数。对于奖励积分，您的解决方案应在N*log(N)时间或更快时间内运行。你可以假设N总是一个正整数。打印出小于给定数字的素数N

输入样本：

您的程序应该接受第一个参数作为文件名的路径。这个文件中的每一行都是一个测试用例。每个测试用例将包含一个整数n < 4,294,967,295。

E.g.

10 
20 
100

输出样本：

对于输入的每一行，打印出素数小于N，以升序，逗号分隔。（逗号和数字之间不应有空格）

2,3,5,7 

2,3,5,7,11,13,17,19 

2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97

这里是我的解决方案：

public class problem1 { 

    public static void main(String [] args) throws Exception 
    { 
     File f=new File("C://Users/Rahul/Documents/Projects/r.txt"); 
     FileReader fr=new FileReader(f); 

     List<Integer> l=new ArrayList<>(); 
     int p; 
     BufferedReader br = new BufferedReader(fr); 
     String s; 

     while((s= br.readLine()) != null) { 

        int a=Integer.parseInt(s); 

        for(int i=2;i<a;i++) 
        { 
         p=0; 
         for(int j=2;j<i;j++) 
         { 
          if(i%j==0) 
          p=1; 
         } 
        if(p==0) 
         l.add(i); 
        } 
        String st=l.toString(); 
        st=st.replaceAll("\\[", "").replaceAll("\\]", "").replace(", ", ","); 
        System.out.print(st); 
        System.out.println("\t"); 
     } 

     fr.close(); 
    } 
}

我输入的是：

10 
50

和输出是：

2,3,5,7 
2,3,5,7,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47

但是，当我提出这个解决方案，他们不接受这个解决方案。

但是当我把内容文件是这样的：

10 50 
30

我想的是java程序忽略这50怎么办呢？

有没有更好的解决方案呢？给我一些想法！

来源

2013-08-03 Rahul Kulhari

看看[Eratosthenes的筛子]（http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes） –

我在说复杂性。 –

你的方法是N^2，在这方面真的很差N^2。筛分方法运作良好。 CodeEval.com的实际数字很小 - 大约为1000.我的提交使用了Sundaram的Sieve，并在0.03秒内跑完。在Java中，我希望它更像0.1 - 0.2，它应该仍然有足够的分数。即使我的Java版本也能快速计算出2000万个，其大部分时间只是打印输出。 –

要忽略文件中的额外数字，您只能取每行的第一个数字。

您的解决方案很可能无法接受，因为在你的第二行已打印2,3,5,7的两倍（即前行的素数）

请参见下面的例子来解决这两个问题

while((s= br.readLine()) != null) { 
    String [] numbers = s.split(" ");  // split the line 
    int a = Integer.parseInt(numbers[0]); // take only the first one 
    .... 

    System.out.print(st); 
    System.out.println("\t"); 
    l.clear(); // clear the list before trying to find primes for the new line 
}

来源

2013-08-03 11:34:16

“你程序应接受作为第一个参数的文件名“

您的解决方案中有硬编码的文件名 - 使用args[0]代替。

不管怎样，您的解决方案看起来不错，尽管在效率方面还有一些改进空间。

来源

2013-08-03 12:06:49

打印出小于给定数字的素数N

回答

相关问题