fork(5) download
copy 
  1. import java.util.List;
  2. import java.io.IOException;
  3. import java.io.OutputStreamWriter;
  4. import java.util.Arrays;
  5. import java.io.BufferedWriter;
  6. import java.util.InputMismatchException;
  7. import java.util.ArrayList;
  8. import java.io.OutputStream;
  9. import java.io.PrintWriter;
  10. import java.io.Writer;
  11. import java.util.AbstractCollection;
  12. import java.math.BigInteger;
  13. import java.util.HashSet;
  14. import java.util.Collection;
  15. import java.io.InputStream;
  16.  
  17. /**
  18.  * Built using CHelper plug-in
  19.  * Actual solution is at the top
  20.  * @author sandeepandey
  21.  */
  22. public class Main {
  23. 	public static void main(String[] args) {
  24. 		InputStream inputStream = System.in;
  25. 		OutputStream outputStream = System.out;
  26. 		InputReader in = new InputReader(inputStream);
  27. 		OutputWriter out = new OutputWriter(outputStream);
  28. 		PrimeGenerator solver = new PrimeGenerator();
  29. 		int testCount = Integer.parseInt(in.next());
  30. 		for (int i = 1; i <= testCount; i++)
  31. 			solver.solve(i, in, out);
  32. 		out.close();
  33. 	}
  34. }
  35.  
  36. class PrimeGenerator {
  37.  
  38.     private static final int MAX_SIZE       =   1000000000;
  39.     private static final int SQRT_LIMIT     = (int) (Math.sqrt(MAX_SIZE*1.0) + 1);
  40.     private static Long[] primes     =   null;
  41.     private static HashSet<Long> lookUp  =   new HashSet<Long>();
  42.     static {
  43.         primes  = IntegerUtils.doFastSieve(SQRT_LIMIT);
  44.         lookUp.addAll(Arrays.asList(primes));
  45.     }
  46.  
  47.  
  48.  
  49.     public void solve(int testNumber, InputReader in, OutputWriter out) {
  50.  
  51.         long start  =   in.readLong();
  52.         long end    =   in.readLong();
  53.         if(start==  1) {
  54.             start++;
  55.         }
  56.         if(start > end) {
  57.             return;
  58.         }
  59.         long[] array    =   new long[(int) (end-start+1)];
  60.         for(int i   =   0; i < (end-start+1) ; i++) {
  61.             array[i]    =   start+i ;
  62.         }
  63.  
  64.         boolean[] fromChoose    =   doProcess(array);
  65.         for(int i   =   0; i < fromChoose.length ; i++) {
  66.                 if(fromChoose[i]) {
  67.                     out.printLine(array[i]);
  68.                 }
  69.         }
  70.     }
  71.  
  72.     private boolean[] doProcess(long[] array) {
  73.  
  74.         boolean[] helper    =   new boolean[array.length];
  75.         Arrays.fill(helper,true);
  76.         long fromCheck  =   array[array.length-1];
  77.         for(int i   =   0; i < primes.length && (long)(primes[i] * primes[i]) <= fromCheck ; i++) {
  78.  
  79.             int startPos    =   getStartPos(array[0],primes[i]);
  80.            // System.out.println("startpos ::"+array[startPos]);
  81.             if((lookUp.contains(array[startPos]))) {
  82.                 startPos += primes[i];
  83.                // System.out.println("startpos ::"+startPos);
  84.             }
  85.             for(int j   =   startPos ; j < array.length ; j+=primes[i]) {
  86.                  helper[j]  =   false;
  87.             }
  88.         }
  89.         return helper;
  90.  
  91.  
  92.  
  93.  
  94.  
  95.     }
  96.  
  97.     private int getStartPos(long start,long prime) {
  98.  
  99.         return (start%prime)  ==  0 ? 0 : ((int) (prime - start % prime));
  100.     }
  101. }
  102.  
  103. class IntegerUtils {
  104.  
  105.     private static char[]   mark    =   new char[0];
  106.     private static List<Long> primes    =   null;
  107.  
  108.  
  109.     //------------------------------------------------------------------------
  110.  
  111.  
  112.     //---------------------------------------------------------------
  113.  
  114.     /**
  115.      * This method will compute the prime number under supplied limit.
  116.      * @param upTo
  117.      * @return
  118.      */
  119.     public static Long[] doFastSieve(int upTo){
  120.         mark=new char[upTo/2/8+1];
  121.         primes  =   new ArrayList<Long>();
  122.         for (int i = 3; i*i <=upTo; i += 2)
  123.             if ( (mark[i>>4] & (1<<((i>>1)&7))) == 0 )
  124.                 for (int j = i*i; j <=upTo; j += i<<1) mark[j>>4] |= (1<<((j>>1)&7));
  125.         primes.add(2l);
  126.         for (int i = 3; i <=upTo; i += 2)
  127.             if ( (mark[i>>4]&(1<<((i>>1)&7))) == 0) {
  128.                 primes.add(Long.valueOf(i));
  129.             }
  130.         return primes.toArray(new Long[primes.size()]);
  131.     }
  132.  
  133.  
  134.  
  135.  
  136. }
  137.  
  138. class InputReader {
  139.  
  140.     private InputStream stream;
  141.  
  142.     private byte[] buf = new byte[1024];
  143.  
  144.     private int curChar;
  145.  
  146.     private int numChars;
  147.  
  148.     private SpaceCharFilter filter;
  149.     public InputReader(InputStream stream) {
  150.  
  151.         this.stream = stream;
  152.  
  153.     }
  154.  
  155.  
  156.  
  157.     public int read() {
  158.  
  159.         if (numChars == -1)
  160.  
  161.             throw new InputMismatchException();
  162.  
  163.         if (curChar >= numChars) {
  164.  
  165.             curChar = 0;
  166.  
  167.             try {
  168.  
  169.                 numChars = stream.read(buf);
  170.  
  171.             } catch (IOException e) {
  172.  
  173.                 throw new InputMismatchException();
  174.  
  175.             }
  176.  
  177.             if (numChars <= 0)
  178.  
  179.                 return -1;
  180.  
  181.         }
  182.  
  183.         return buf[curChar++];
  184.  
  185.     }
  186.  
  187.  
  188.  
  189.     public long readLong() {
  190.  
  191.         int c = read();
  192.  
  193.         while (isSpaceChar(c))
  194.  
  195.             c = read();
  196.  
  197.         int sgn = 1;
  198.  
  199.         if (c == '-') {
  200.  
  201.             sgn = -1;
  202.  
  203.             c = read();
  204.  
  205.         }
  206.  
  207.         long res = 0;
  208.  
  209.         do {
  210.  
  211.             if (c < '0' || c > '9')
  212.  
  213.                 throw new InputMismatchException();
  214.  
  215.             res *= 10;
  216.  
  217.             res += c - '0';
  218.  
  219.             c = read();
  220.  
  221.         } while (!isSpaceChar(c));
  222.  
  223.         return res * sgn;
  224.  
  225.     }
  226.  
  227.  
  228.  
  229.     public String readString() {
  230.  
  231.         int c = read();
  232.  
  233.         while (isSpaceChar(c))
  234.  
  235.             c = read();
  236.  
  237.         StringBuffer res = new StringBuffer();
  238.  
  239.         do {
  240.  
  241.             res.appendCodePoint(c);
  242.  
  243.             c = read();
  244.  
  245.         } while (!isSpaceChar(c));
  246.  
  247.         return res.toString();
  248.  
  249.     }
  250.  
  251.  
  252.  
  253.     public boolean isSpaceChar(int c) {
  254.  
  255.         if (filter != null)
  256.  
  257.             return filter.isSpaceChar(c);
  258.  
  259.         return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
  260.  
  261.     }
  262.  
  263.  
  264.  
  265.     public String next() {
  266.  
  267.         return readString();
  268.  
  269.     }
  270.  
  271.  
  272.  
  273.     public interface SpaceCharFilter {
  274.  
  275.         public boolean isSpaceChar(int ch);
  276.  
  277.     }
  278.  
  279. }
  280.  
  281. class OutputWriter {
  282.  
  283.     private final PrintWriter writer;
  284.     public OutputWriter(OutputStream outputStream) {
  285.  
  286.         writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
  287.  
  288.     }
  289.  
  290.  
  291.  
  292.     public OutputWriter(Writer writer) {
  293.         this.writer = new PrintWriter(writer);
  294.     }
  295.  
  296.  
  297.  
  298.     public void print(Object...objects) {
  299.  
  300.         for (int i = 0; i < objects.length; i++) {
  301.  
  302.             if (i != 0)
  303.  
  304.                 writer.print(' ');
  305.  
  306.             writer.print(objects[i]);
  307.  
  308.         }
  309.  
  310.     }
  311.  
  312.  
  313.  
  314.     public void printLine(Object...objects) {
  315.  
  316.         print(objects);
  317.  
  318.         writer.println();
  319.  
  320.     }
  321.  
  322.  
  323.  
  324.     public void close() {
  325.  
  326.         writer.close();
  327.  
  328.     }
  329.  
  330.  
  331.  
  332.     }
  333.  
  334.  
  335.  
Runtime error #stdin #stdout #stderr 0.08s 380224KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Exception in thread "main" java.util.InputMismatchException
	at InputReader.read(Main.java:161)
	at InputReader.readString(Main.java:235)
	at InputReader.next(Main.java:267)
	at Main.main(Main.java:29)
https://ideone.com/ldIsOX
language:
Java (12.0.1)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!