115 . 小 Cheng 發現 ${}_6{}^7$ 的秘密

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

ItzYouLingTW
我跟 AP、AC 的距離，比我跟他的距離近

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

100.0% (1/1)

Tags

埃氏篩 Sieve of Eratosthenes

Description

小 Cheng在學校上數學課，他上到了質數這個東東，老師說：「當某個數 $k$ 的因數只有 $1$ 以及 $k$，則 $k$ 就是質數。」

於是小 Cheng 想要把所有 $1 \sim 100$ 的質數全部列出來。他在這個過程中，他發現 $67$ 是質數，他很快樂，且 $67$ 是第 $19$ 個質數，而且 $19$ 竟然也是質數。
他上網查後，發現這個東西竟然叫做「超質數」。

「超質數」就是這個數是第質數個質數，就是超質數。
小 Cheng想要知道數字 A 到數字 B 之間(包含 $A ,\ B$)有幾個超質數，不過他很懶，他想要請你幫忙寫一個程式，算出從 A 到 B 有幾個「超質數」。

對於所有測試資料：
$1 \le A \lt B \le 5 \times 10$$5$

Input Format

輸入共兩個數字，分別表示 $A ,\ B$。

Output Format

輸出僅一個數字，代表 $A$ 到 $B$ 之間有多少個質數。

Sample Input 1


        

      

    

    

      

        

          
Sample Output 1

            
        

        

            

        

      

    

  




  

    

      

        
Hints

      

      

        
      

    

  

  

    

      

        
Problem Source

      

      

        
      

    

  






  

    
Subtasks

  

  

    
      

        No.
        Testdata Range
        Score
      

    
  






  

    

      Testdata and Limits
      
    

  

  

  

    
      

        No.
        Time Limit (ms)
          Memory Limit (VSS, KiB) 
        Output Limit (KiB)
        Subtasks
      

    
    
        

          0
          1000
            65536
          65536
          
          
        

        

          1
          1000
            65536
          65536
          
          
        

        

          2
          1000
            65536
          65536
          
          
        

        

          3
          1000
            65536
          65536
          
          
        

        

          4
          1000
            65536
          65536
          
          
        

    
  

  






    

    Submit
  


  

    Back to Top