# Print characters at prime indices — Asked in Accenture Interview

# Problem Statement :

You are given a string ‘str’, you need to return a string which will contain all the characters present at the prime indices of the original string. The relative order of characters in the new string should be exactly the same as it was in the original string.

**Sample Input:**

`AmazonGoogleMicrosoftNetflix`

**Sample Output:**

`aznoeisft`

# Approach :

# Sieve of Eratosthenes.

- Let’s first understand the sieve of Eratosthenes to find primes efficiently.
- Since 2 is the smallest prime number, if string str length < 2, then return an empty string as the answer.
- In the sieve of Eratosthenes, we create a list of prime numbers from 2 to N, where N is the length of the string.
- Initialize all list elements as prime, as initially, we assume that all numbers from 2 to N are prime
- Start with prime = 2, If a prime is marked to true, mark all its multiples as non-primes, i.e. from >= 2*prime, till the end of the list.
- Non-primes will be {2*prime, 3*prime, … prime*prime, prime*(prime+1), prime*(prime+2), prime(prime+3), …} till index N-1 because all such indices have a common factor: prime so that all such numbers will be divisible by prime as well.
- After calculating primes in the list, iterate through the list from 2 to N-1. If the current index is marked as prime, append the character at this index to the answer string solution.

Time Complexity : O(Nlog(log N))

Space Complexity : O(N)