{"id":"6bbe8a60-fd3f-4422-80bb-3de1c2dc3551","name":"Segmented Sieve","description":"1. Generate all primes between 'a' and 'b'(both are included).\r\n2. Print every number in new line.\r\n3. Allowed time Complexity : O(nlog(log n)), where n = b - a.\r\n4. Allowed Space Complexity : O(n), where n = b -a;\r\nNote : Please focus on constraints.\r\n","inputFormat":"(Input is managed for you)\r\n22\r\n51\r\n","outputFormat":"23\r\n29\r\n31\r\n37\r\n41\r\n43\r\n47","constraints":"1. 1 &lt;= a &lt;= b &lt;= 10^9\r\n2. b - a &lt;= 10^5\r\n","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\n\n // ~~~~~~~~~~~~~User Section~~~~~~~~~~~~\n vector<int> sieveOfEratosthenes(int N) {\n //write your code here\n }\n\nvoid segmentedSieveAlgo(int a, int b) {\n // write your code here\n }\n\n // ~~~~~~~~~~~~Input Management~~~~~~~~~~~\n int main() {\n \n int a,b;\n cin>>a;\n cin>>b;\n segmentedSieveAlgo(a, b);\n }"},"java":{"code":"import java.util.*;\r\n\r\npublic class Main {\r\n\r\n // ~~~~~~~~~~~~~User Section~~~~~~~~~~~~\r\n\r\n public static void segmentedSieveAlgo(int a, int b) {\r\n // write your code here\r\n }\r\n\r\n // ~~~~~~~~~~~~Input Management~~~~~~~~~~~\r\n public static void main(String[] args) {\r\n Scanner scn = new Scanner(System.in);\r\n int a = scn.nextInt();\r\n int b = scn.nextInt();\r\n segmentedSieveAlgo(a, b);\r\n }\r\n}\r\n"},"python":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"22\r\n51","sampleOutput":"23\r\n29\r\n31\r\n37\r\n41\r\n43\r\n47","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"35f2cfb0-6f25-4967-b0c9-92f2384b9260","name":"Arrays And Strings For Intermediate","slug":"arrays-and-strings-for-intermediate-732","type":0},{"id":"a47c51b9-d7b8-42ad-8cf0-6dca60460579","name":"Segmented Sieve","slug":"segmented-sieve","type":1}],"next":{"id":"9d0f834d-98c7-4bd6-9199-306af8f849f4","name":"Segmented Sieve","type":3,"slug":"segmented-sieve"},"prev":{"id":"55a6ea7b-dd3a-4c49-9a14-d5aaa1de2909","name":"Sieve Of Eratosthenes MCQ","type":0,"slug":"sieve-of-eratosthenes-mcq"}}}

Segmented Sieve

1. Generate all primes between 'a' and 'b'(both are included). 2. Print every number in new line. 3. Allowed time Complexity : O(nlog(log n)), where n = b - a. 4. Allowed Space Complexity : O(n), where n = b -a; Note : Please focus on constraints.

{"id":"6bbe8a60-fd3f-4422-80bb-3de1c2dc3551","name":"Segmented Sieve","description":"1. Generate all primes between 'a' and 'b'(both are included).\r\n2. Print every number in new line.\r\n3. Allowed time Complexity : O(nlog(log n)), where n = b - a.\r\n4. Allowed Space Complexity : O(n), where n = b -a;\r\nNote : Please focus on constraints.\r\n","inputFormat":"(Input is managed for you)\r\n22\r\n51\r\n","outputFormat":"23\r\n29\r\n31\r\n37\r\n41\r\n43\r\n47","constraints":"1. 1 &lt;= a &lt;= b &lt;= 10^9\r\n2. b - a &lt;= 10^5\r\n","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\n\n // ~~~~~~~~~~~~~User Section~~~~~~~~~~~~\n vector<int> sieveOfEratosthenes(int N) {\n //write your code here\n }\n\nvoid segmentedSieveAlgo(int a, int b) {\n // write your code here\n }\n\n // ~~~~~~~~~~~~Input Management~~~~~~~~~~~\n int main() {\n \n int a,b;\n cin>>a;\n cin>>b;\n segmentedSieveAlgo(a, b);\n }"},"java":{"code":"import java.util.*;\r\n\r\npublic class Main {\r\n\r\n // ~~~~~~~~~~~~~User Section~~~~~~~~~~~~\r\n\r\n public static void segmentedSieveAlgo(int a, int b) {\r\n // write your code here\r\n }\r\n\r\n // ~~~~~~~~~~~~Input Management~~~~~~~~~~~\r\n public static void main(String[] args) {\r\n Scanner scn = new Scanner(System.in);\r\n int a = scn.nextInt();\r\n int b = scn.nextInt();\r\n segmentedSieveAlgo(a, b);\r\n }\r\n}\r\n"},"python":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"22\r\n51","sampleOutput":"23\r\n29\r\n31\r\n37\r\n41\r\n43\r\n47","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"35f2cfb0-6f25-4967-b0c9-92f2384b9260","name":"Arrays And Strings For Intermediate","slug":"arrays-and-strings-for-intermediate-732","type":0},{"id":"a47c51b9-d7b8-42ad-8cf0-6dca60460579","name":"Segmented Sieve","slug":"segmented-sieve","type":1}],"next":{"id":"9d0f834d-98c7-4bd6-9199-306af8f849f4","name":"Segmented Sieve","type":3,"slug":"segmented-sieve"},"prev":{"id":"55a6ea7b-dd3a-4c49-9a14-d5aaa1de2909","name":"Sieve Of Eratosthenes MCQ","type":0,"slug":"sieve-of-eratosthenes-mcq"}}}
plane

Editor


Loading...

Segmented Sieve

easy

1. Generate all primes between 'a' and 'b'(both are included). 2. Print every number in new line. 3. Allowed time Complexity : O(nlog(log n)), where n = b - a. 4. Allowed Space Complexity : O(n), where n = b -a; Note : Please focus on constraints.

Constraints

1. 1 <= a <= b <= 10^9 2. b - a <= 10^5

Format

Input

(Input is managed for you) 22 51

Output

23 29 31 37 41 43 47

Example

Sample Input

22 51

Sample Output

23 29 31 37 41 43 47

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode