打印出小於給定數字的素數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

回答

相關問題