Given a string S. The task is to count and print the number of characters in the string whose ASCII values are prime.
Examples:
Input: S = “neveropen”
Output : 3
‘g’, ‘e’ and ‘k’ are the only characters whose ASCII values are prime i.e. 103, 101 and 107 respectively.Input: S = “abcdefghijklmnopqrstuvwxyz”
Output: 6
Approach: The idea is to generate all primes upto max ASCII value of character of string S using Sieve of Eratosthenes. Now, Iterate the string and get the ASCII value of each character. If the ASCII value is prime then increment the count. Finally, print the count.
Below is the implementation of the above approach:
C++
// C++ implementation of above approach#include <bits/stdc++.h>using namespace std;#define max_val 257// Function to find prime characters in the stringint PrimeCharacters(string s){ // USE SIEVE TO FIND ALL PRIME NUMBERS LESS // THAN OR EQUAL TO max_val // Create a Boolean array "prime[0..n]". A // value in prime[i] will finally be false // if i is Not a prime, else true. vector<bool> prime(max_val + 1, true); // 0 and 1 are not primes prime[0] = false; prime[1] = false; for (int p = 2; p * p <= max_val; p++) { // If prime[p] is not changed, then // it is a prime if (prime[p] == true) { // Update all multiples of p for (int i = p * 2; i <= max_val; i += p) prime[i] = false; } } int count = 0; // Traverse all the characters for (int i = 0; i < s.length(); ++i) { if (prime[int(s[i])]) count++; } return count;}// Driver programint main(){ string S = "neveropen"; // print required answer cout << PrimeCharacters(S); return 0;} |
Java
// Java implementation of above approach class Solution{static final int max_val=257; // Function to find prime characters in the String static int PrimeCharacters(String s) { // USE SIEVE TO FIND ALL PRIME NUMBERS LESS // THAN OR EQUAL TO max_val // Create a Boolean array "prime[0..n]". A // value in prime[i] will finally be false // if i is Not a prime, else true. boolean prime[]= new boolean[max_val+1]; //initialize the value for(int i=0;i<=max_val;i++) prime[i]=true; // 0 and 1 are not primes prime[0] = false; prime[1] = false; for (int p = 2; p * p <= max_val; p++) { // If prime[p] is not changed, then // it is a prime if (prime[p] == true) { // Update all multiples of p for (int i = p * 2; i <= max_val; i += p) prime[i] = false; } } int count = 0; // Traverse all the characters for (int i = 0; i < s.length(); ++i) { if (prime[(int)(s.charAt(i))]) count++; } return count; } // Driver program public static void main(String args[]){ String S = "neveropen"; // print required answer System.out.print( PrimeCharacters(S)); } }//contributed by Arnab Kundu |
Python3
# Python3 implementation of above approach from math import sqrtmax_val = 257# Function to find prime characters in the string def PrimeCharacters(s) : # USE SIEVE TO FIND ALL PRIME NUMBERS LESS # THAN OR EQUAL TO max_val # Create a Boolean array "prime[0..n]". A # value in prime[i] will finally be false # if i is Not a prime, else true. prime = [True] * (max_val + 1) # 0 and 1 are not primes prime[0] = False prime[1] = False for p in range(2, int(sqrt(max_val)) + 1) : # If prime[p] is not changed, then # it is a prime if (prime[p] == True) : # Update all multiples of p for i in range(2*p ,max_val + 1, p) : prime[i] = False count = 0 # Traverse all the characters for i in range(len(s)) : if (prime[ord(s[i])]) : count += 1 return count # Driver program if __name__ == "__main__" : S = "neveropen"; # print required answer print(PrimeCharacters(S)) # This code is contributed by Ryuga |
C#
// C# implementation of above approach using System;class GFG{ static readonly int max_val = 257; // Function to find prime characters in the String static int PrimeCharacters(String s) { // USE SIEVE TO FIND ALL PRIME NUMBERS LESS // THAN OR EQUAL TO max_val // Create a Boolean array "prime[0..n]". A // value in prime[i] will finally be false // if i is Not a prime, else true. bool []prime = new bool[max_val + 1]; //initialize the value for(int i = 0; i <= max_val; i++) prime[i] = true; // 0 and 1 are not primes prime[0] = false; prime[1] = false; for (int p = 2; p * p <= max_val; p++) { // If prime[p] is not changed, then // it is a prime if (prime[p] == true) { // Update all multiples of p for (int i = p * 2; i <= max_val; i += p) prime[i] = false; } } int count = 0; // Traverse all the characters for (int i = 0; i < s.Length; ++i) { if (prime[(int)(s[i])]) count++; } return count; } // Driver Codepublic static void Main() { String S = "neveropen"; // print required answer Console.Write( PrimeCharacters(S)); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // JavaScript implementation of above approach const max_val = 257; // Function to find prime characters in the String function PrimeCharacters(s) { // USE SIEVE TO FIND ALL PRIME NUMBERS LESS // THAN OR EQUAL TO max_val // Create a Boolean array "prime[0..n]". A // value in prime[i] will finally be false // if i is Not a prime, else true. var prime = new Array(max_val + 1); //initialize the value for (var i = 0; i <= max_val; i++) prime[i] = true; // 0 and 1 are not primes prime[0] = false; prime[1] = false; for (var p = 2; p * p <= max_val; p++) { // If prime[p] is not changed, then // it is a prime if (prime[p] === true) { // Update all multiples of p for (var i = p * 2; i <= max_val; i += p) prime[i] = false; } } var count = 0; // Traverse all the characters for (var i = 0; i < s.length; ++i) { if (prime[s[i].charCodeAt(0)]) count++; } return count; } // Driver Code var S = "neveropen"; // print required answer document.write(PrimeCharacters(S)); // This code is contributed by rdtank. </script> |
Output
8
Complexity Analysis:
- Time Complexity: O(max_val*log(log(max_val)))
- Auxiliary Space: O(max_val)
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!
