Given an integer N, the task is to generate an array of size N with the following properties:
- No two elements divide each other.
- Every odd subset has an odd sum and every even subset has an even sum.
Examples:
Input: N = 3
Output: 3 5 7
No two element divide each other and the sum
of all the odd subsets {3}, {5}, {7} and {3, 5, 7} is odd.
Sum of all the even subsets is even i.e. {3, 5}, {3, 7} and {5, 7}
Input: N = 6
Output: 3 5 7 11 13 17
Approach: In order to satisfy the condition when every odd subset has an odd sum and even a subset has an even sum, every element has to be odd and in order for any two elements to not divide each other they must be prime. So, the task now is to find the first N odd prime numbers.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;#define MAX 1000000// Create a boolean array "prime[0..n]" and initialize// all entries it as true. A value in prime[i] will// finally be false if i is Not a prime, else true.bool prime[MAX + 1];void SieveOfEratosthenes(){ memset(prime, true, sizeof(prime)); prime[1] = false; for (int p = 2; p * p <= MAX; p++) { // If prime[p] is not changed, then it is a prime if (prime[p] == true) { // Set all multiples of p to non-prime for (int i = p * 2; i <= MAX; i += p) prime[i] = false; } }}// Function to find the first// n odd prime numbersvoid solve(int n){ // To store the current count // of prime numbers int count = 0; // Starting with 3 as 2 is // an even prime number for (int i = 3; count < n; i++) { // If i is prime if (prime[i]) { // Print i and increment count cout << i << " "; count++; } }}// Driver codeint main(){ // Create the sieve SieveOfEratosthenes(); int n = 6; solve(n); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG {static int MAX = 1000000;// Create a boolean array "prime[0..n]" and // initialize all entries it as true. // A value in prime[i] will finally be false// if i is Not a prime, else true.static boolean []prime = new boolean[MAX + 1];static void SieveOfEratosthenes(){ for (int i = 0; i <= MAX; i ++) prime[i] = true; prime[1] = false; for (int p = 2; p * p <= MAX; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true) { // Set all multiples of p to non-prime for (int i = p * 2; i <= MAX; i += p) prime[i] = false; } }}// Function to find the first// n odd prime numbersstatic void solve(int n){ // To store the current count // of prime numbers int count = 0; // Starting with 3 as 2 is // an even prime number for (int i = 3; count < n; i++) { // If i is prime if (prime[i]) { // Print i and increment count System.out.print(i + " "); count++; } }}// Driver codepublic static void main(String[] args) { // Create the sieve SieveOfEratosthenes(); int n = 6; solve(n);}} // This code is contributed by Rajput-Ji |
Python3
# Python3 implementation of the approach from math import sqrtMAX = 1000000# Create a boolean array "prime[0..n]" and # initialize all entries it as true. # A value in prime[i] will finally be false# if i is Not a prime, else true. prime = [True] * (MAX + 1); def SieveOfEratosthenes() : prime[1] = False; for p in range(2, int(sqrt(MAX)) + 1) : # If prime[p] is not changed, # then it is a prime if (prime[p] == True) : # Set all multiples of p to non-prime for i in range(p * 2, MAX + 1, p) : prime[i] = False; # Function to find the first # n odd prime numbers def solve(n) : # To store the current count # of prime numbers count = 0; i = 3; # Starting with 3 as 2 is # an even prime number while count < n : # If i is prime if (prime[i]) : # Print i and increment count print(i, end = " "); count += 1; i += 1# Driver code if __name__ == "__main__" : # Create the sieve SieveOfEratosthenes(); n = 6; solve(n); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the above approach using System; class GFG {static int MAX = 1000000;// Create a boolean array "prime[0..n]" and // initialize all entries it as true. // A value in prime[i] will finally be false// if i is Not a prime, else true.static bool []prime = new bool[MAX + 1];static void SieveOfEratosthenes(){ for (int i = 0; i <= MAX; i ++) prime[i] = true; prime[1] = false; for (int p = 2; p * p <= MAX; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true) { // Set all multiples of p to non-prime for (int i = p * 2; i <= MAX; i += p) prime[i] = false; } }}// Function to find the first// n odd prime numbersstatic void solve(int n){ // To store the current count // of prime numbers int count = 0; // Starting with 3 as 2 is // an even prime number for (int i = 3; count < n; i++) { // If i is prime if (prime[i]) { // Print i and increment count Console.Write(i + " "); count++; } }}// Driver codepublic static void Main(String[] args) { // Create the sieve SieveOfEratosthenes(); int n = 6; solve(n);}}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript implementation of the approachconst MAX = 1000000;// Create a boolean array "prime[0..n]" and initialize// all entries it as true. A value in prime[i] will// finally be false if i is Not a prime, else true.let prime = new Array(MAX + 1).fill(true);function SieveOfEratosthenes(){ prime[1] = false; for (let p = 2; p * p <= MAX; p++) { // If prime[p] is not changed, then it is a prime if (prime[p] == true) { // Set all multiples of p to non-prime for (let i = p * 2; i <= MAX; i += p) prime[i] = false; } }}// Function to find the first// n odd prime numbersfunction solve(n){ // To store the current count // of prime numbers let count = 0; // Starting with 3 as 2 is // an even prime number for (let i = 3; count < n; i++) { // If i is prime if (prime[i]) { // Print i and increment count document.write(i + " "); count++; } }}// Driver code // Create the sieve SieveOfEratosthenes(); let n = 6; solve(n);</script> |
Output:
3 5 7 11 13 17
Time Complexity: O(n + MAX3/2)
Auxiliary Space: O(MAX)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
