+
Given a string S, the task is to print all words with prime length in the given string.
Examples:
Input: S = “This is a python programming language”
Output: is
programming
Explanation: Length of is is 2 and length of programming is 11 both are primesInput: S = “You are using neveropen”
Output: You
are
using
neveropen
Approach 1:
To solve the problem follow the below steps:
- First, split the given string to get an array of space-separated strings.
- Start traversing the words from left to right.
- Calculate the length of each word.
- If the length is prime, then print the word.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;bool isPrime(int x){ // This flag maintains status whether the // x is prime or not int prime = 0; if (x == 2) return 1; if (x > 1) { for (int i = 2; i < sqrt(x) + 1; i++) { if (x % i == 0) { prime = 1; break; } } if (prime == 0) return true; else return false; } else return false;}void printPrimeLenWords(string& s){ s += ' '; string temp; for (int i = 0; i < s.length(); i++) { if (s[i] == ' ') { // Checking if length of the word // is prime if (isPrime(temp.size())) { cout << temp << "\n"; } temp = ""; } else temp += s[i]; }}// Driver Codeint main(){ string s = "This is a python programming language"; printPrimeLenWords(s); return 0;}// This code is contributed by Rohit Pradhan |
Java
/*package whatever //do not write package name here */import java.io.*; class GFG { public static boolean isPrime(int x) { // This flag maintains status whether the // x is prime or not int prime = 0; if (x == 2) return true; if (x > 1) { for (int i = 2; i < Math.sqrt(x) + 1; i++) { if (x % i == 0) { prime = 1; break; } } if (prime == 0) return true; else return false; } else return false; } public static void printPrimeLenWords(String s) { s += " "; String temp = ""; for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == ' ') { // Checking if length of the word // is prime if (isPrime(temp.length())) { System.out.println(temp); } temp = ""; } else temp += s.charAt(i); } } public static void main(String[] args) { String s = "This is a python programming language"; printPrimeLenWords(s); }} // This code is contributed by aadityaburujwale. |
Python3
# Python program to print all words with# prime length in the given string. # Function to check element is primefrom math import sqrt def isPrime(x):# This flag maintains status whether the# x is prime or not prime = 0 if(x > 1): for i in range(2, int(sqrt(x)) + 1): if (x % i == 0): prime = 1 break if (prime == 0): return True else: return False else: return False def printPrimeLenWords(s): # Splitting the sentence at spaces s = s.split() for i in s: # Checking if length of the word # is prime if isPrime(len(i)): print(i) # Driver codeif __name__ == '__main__': st = "This is a python programming language" # Function call printPrimeLenWords(st) |
C#
using System;public class GFG { public static bool isPrime(int x) { // This flag maintains status whether the // x is prime or not int prime = 0; if (x == 2) return true; if (x > 1) { for (int i = 2; i < Math.Sqrt(x) + 1; i++) { if (x % i == 0) { prime = 1; break; } } if (prime == 0) return true; else return false; } else return false; } public static void printPrimeLenWords(string s) { s += ' '; string temp = ""; for (int i = 0; i < s.Length; i++) { if (s[i] == ' ') { // Checking if length of the word // is prime if (isPrime(temp.Length)) { Console.WriteLine(temp); } temp = ""; } else temp += s[i]; } } // Driver Code static public void Main() { string s = "This is a python programming language"; printPrimeLenWords(s); }} // This code is contributed by akashish__ |
Javascript
// JavaScript code for the above approach // Function to check element is prime function isPrime(x) { // This flag maintains status whether the // x is prime or not prime = 0 if (x == 2) return 1 if (x > 1) { for (let i = 2; i < Math.sqrt(x) + 1; i++) { if (x % i == 0) { prime = 1 break } } if (prime == 0) return true else return false } else return false } function printPrimeLenWords(s) { // Splitting the sentence at spaces s = s.split(' ') for (let i = 0; i < s.length; i++) // Checking if length of the word // is prime if (isPrime(s[i].length)) console.log(s[i]) } // Driver code st = "This is a python programming language" // Function call printPrimeLenWords(st) // This code is contributed by Potta Lokesh |
Output
is programming
Time complexity: O(n * sqrt(x)), where n is the number of words in the given sentence and x be the length of the largest string.
Auxiliary Space: O(1)
Approach 2:
Step 1: Initially store all the prime number uptill the pow(10, 5) using the Sieve of Eratosthenes into a set data structure.
Step 2: Run the for loop for every word and search the length of that word into the set.
Step 3: If word length is present then print else continue.
Implementation for the above approach : –
C++
// C++ Implementation for the above approach#include<bits/stdc++.h>using namespace std;void SieveOfEratosthenes(int n, set<int> &store){ bool prime[n+1]; memset(prime, true, sizeof(prime)); for (int p=2; p*p<=n; 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<=n; i += p) prime[i] = false; } } // Print all prime numbers for (int p=2; p<=n; p++) if (prime[p]) store.insert(p);}int main(){ set<int> store; string s = "This is a python programming language"; SieveOfEratosthenes(s.size(), store); // for getting the every word from the sentence istringstream iss(s); string word; // looping for extracting the every word length while(iss >> word){ if(store.find(word.size()) != store.end()){ cout << word << endl; } } return 0;} |
Java
// Java Implementation for the above approachimport java.io.*;import java.util.*;class GFG { static Set<Integer> store = new HashSet<>(); static void SieveOfEratosthenes(int n) { boolean[] prime = new boolean[n + 1]; Arrays.fill(prime, true); for (int p = 2; p * p <= n; p++) { // If prime[p] is not changed, then it is a // prime if (prime[p] == true) { for (int i = p * 2; i <= n; i += p) { prime[i] = false; } } } // Print all prime numbers for (int p = 2; p <= n; p++) { if (prime[p]) { store.add(p); } } } public static void main(String[] args) { String s = "This is a python programming language"; SieveOfEratosthenes(s.length()); // for getting the every word from the sentence String[] words = s.split(" "); // looping for extracting the every word length for (String word : words) { if (store.contains(word.length())) { System.out.println(word); } } }}// This code is contributed by karthik. |
Python3
# Python Implementation for the above approachdef SieveOfEratosthenes( n, store): prime=[1]*(n+1); p=2; while(p*p<=n): # 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, n+1, p): prime[i] = False; p+=1; # Print all prime numbers for p in range(2,n+1,1): if (prime[p]): store.add(p);store=set();s = "This is a python programming language";SieveOfEratosthenes(len(s), store); # for getting the every word from the sentencewords=s.split(); # looping for extracting the every word lengthfor i in range (0,len(words)): #if(store.find(word.size()) != store.end()){ word=words[i]; if(len(word) in store): print(word); |
C#
// C# Implementation for the above approachusing System;using System.Collections.Generic;public class GFG { static HashSet<int> store = new HashSet<int>(); static void SieveOfEratosthenes(int n) { bool[] prime = new bool[n + 1]; for (int i = 0; i <= n; i++) { prime[i] = true; } for (int p = 2; p * p <= n; p++) { if (prime[p] == true) { for (int i = p * 2; i <= n; i += p) { prime[i] = false; } } } for (int p = 2; p <= n; p++) { if (prime[p]) { store.Add(p); } } } static public void Main() { // Code string s = "This is a python programming language"; SieveOfEratosthenes(s.Length); string[] words = s.Split(" "); foreach(string word in words) { if (store.Contains(word.Length)) { Console.WriteLine(word); } } }}// This code is contributed by lokesh. |
Javascript
// JavaScript Implementation for the above approachfunction SieveOfEratosthenes(n, store) { let prime = Array(n + 1).fill(true); for (let p = 2; p * p <= n; p++) { // If prime[p] is not changed, then it is a prime if (prime[p] === true) { // Update all multiples of p for (let i = p * 2; i <= n; i += p) { prime[i] = false; } } } // Print all prime numbers for (let p = 2; p <= n; p++) { if (prime[p]) { store.add(p); } } } let store = new Set(); let s = 'This is a python programming language'; SieveOfEratosthenes(s.length, store); // for getting the every word from the sentence let words = s.split(' '); // looping for extracting the every word length for (let word of words) { if (store.has(word.length)) { document.write(word); document.write("<br>"); } } |
Output
is programming
Time complexity: O(n*log(logn)), where n = size of string
Auxiliary Space: O(n)
Approach 3:
Step 1: Iterate over the characters of the string one by one.
Step 2: Whenever we encounter a space character, we check if the length of the word is prime or not.
Step 3: If it is, we print the word. We also check same for the last word which is not followed by a space character.
Below is the implementation of the above approach.
C++
// C++ Implementation for the above approach#include <bits/stdc++.h>using namespace std;bool isPrime(int p){ if (p <= 1) return false; else if (p == 2 || p == 3) return true; else if (p % 2 == 0 || p % 3 == 0) return false; else { for (int i = 5; i * i <= p; i += 6) { if (p % i == 0 || p % (i + 2) == 0) return false; } } return true;}int main(){ string s = "This is a python programming language"; string word; for (int i = 0; i < s.length(); i++) { if (s[i] != ' ') { word += s[i]; } else { if (isPrime(word.length())) { cout << word << endl; } word.clear(); } } if (isPrime(word.length())) { cout << word << endl; } return 0;}// This code is contributed by Susobhan Akhuli |
Java
// Java Implementation for the above approachimport java.util.*;public class Main { // Function to check whether a number is prime or not static boolean isPrime(int p) { if (p <= 1) return false; else if (p == 2 || p == 3) return true; else if (p % 2 == 0 || p % 3 == 0) return false; else { for (int i = 5; i * i <= p; i += 6) { if (p % i == 0 || p % (i + 2) == 0) return false; } } return true; } public static void main(String[] args) { String s = "This is a python programming language"; String word = ""; // Loop through each character of the input string for (int i = 0; i < s.length(); i++) { if (s.charAt(i) != ' ') { word += s.charAt(i); } else { if (isPrime(word.length())) { System.out.println(word); } word = ""; } } // Check the last word separately since it won't // have a space after it if (isPrime(word.length())) { System.out.println(word); } }}// This code is contributed by rishabmalhdijo |
Python3
import math# Function to check if a number is prime or notdef isPrime(p): if p <= 1: return False elif p == 2 or p == 3: return True elif p % 2 == 0 or p % 3 == 0: return False else: for i in range(5, int(math.sqrt(p)) + 1, 6): if p % i == 0 or p % (i + 2) == 0: return False return Trues = "This is a python programming language"word = ""# Loop through each character in the stringfor i in range(len(s)): if s[i] != " ": word += s[i] else: if isPrime(len(word)): print(word) word = ""# Check if the last word is primeif isPrime(len(word)): print(word) |
C#
// C# Implementation for the above approachusing System;class Gfg{ static bool isPrime(int p) { if (p <= 1) return false; else if (p == 2 || p == 3) return true; else if (p % 2 == 0 || p % 3 == 0) return false; else { for (int i = 5; i * i <= p; i += 6) { if (p % i == 0 || p % (i + 2) == 0) return false; } } return true; } public static void Main() { string s = "This is a python programming language"; string word=""; for (int i = 0; i < s.Length; i++) { if (s[i] != ' ') { word += s[i]; } else { if (isPrime(word.Length)) { Console.WriteLine(word); } word=""; } } if (isPrime(word.Length)) { Console.WriteLine(word); } }} |
Javascript
function isPrime(p) { if (p <= 1) return false; else if (p == 2 || p == 3) return true; else if (p % 2 == 0 || p % 3 == 0) return false; else { for (let i = 5; i * i <= p; i += 6) { if (p % i == 0 || p % (i + 2) == 0) return false; } } return true;}let s = "This is a python programming language";let word = "";for (let i = 0; i < s.length; i++) { if (s[i] != " ") { word += s[i]; } else { if (isPrime(word.length)) { console.log(word); } word = ""; }}if (isPrime(word.length)) { console.log(word);} |
Output
is programming
Time complexity: O(N*sqrt(N)), where N is the length of the string.
Auxiliary Space: O(K), where K is the length of the biggest word in the string.
Approach 4:
Step 1: First split the sentence into words using repeated iteration of getline() function.
Step 2: In each iteration, we check if the length of the word is prime or not using Wilson Primality Test.
Step 3: If it is prime, then we print the word.
C++
// C++ Implementation for the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate the factoriallong long fact(const int& p){ if (p <= 1) return 1; return p * fact(p - 1);}// Function to check if the// number is prime or not// using Wilson Primality Testbool isPrime(const long long& p){ if (p == 4 || p <= 1) return false; // (p - 1) ! ≡ (p-1) mod p long long a = fact(p - 1) % p; if (a == p - 1) return true; return false;}int main(){ string s = "This is a python programming language"; string word; istringstream iss(s); while (getline(iss, word, ' ')) { if (isPrime(word.length())) cout << word << endl; } return 0;}// This code is contributed by Susobhan Akhuli |
Java
// Java Implementation for the above approachimport java.io.*;import java.util.*;public class GFG { // Function to calculate the factorial public static long fact(final int p) { if (p <= 1) { return 1; } return p * fact(p - 1); } // Function to check if the // number is prime or not // using Wilson Primality Test public static boolean isPrime(final long p) { if (p == 4 || p <= 1) { return false; } // (p - 1) ! ≡ (p-1) mod p final long a = fact((int)(p - 1)) % p; if (a == p - 1) { return true; } return false; } public static void main(final String[] args) { final String s = "This is a python programming language"; String word; final Scanner iss = new Scanner(s); iss.useDelimiter(" "); while (iss.hasNext()) { word = iss.next(); if (isPrime(word.length())) { System.out.println(word); } } iss.close(); }}// This code is contributed by Susobhan Akhuli |
Python3
# Python Implementation for the above approach# Function to calculate the factorialdef fact(p): if p <= 1: return 1 return p * fact(p - 1)# Function to check if the# number is prime or not# using Wilson Primality Testdef isPrime(p): if p == 4 or p <= 1: return False # (p - 1) ! ≡ (p-1) mod p a = fact(p - 1) % p if a == p - 1: return True return Falses = "This is a python programming language"words = s.split(' ')for word in words: if isPrime(len(word)): print(word)# This code is contributed by Susobhan Akhuli |
C#
// C# Implementation for the above approachusing System;using System.Linq;using System.Collections.Generic;class Program { // Function to calculate the factorial static long Fact(int p) { if (p <= 1) return 1; return p * Fact(p - 1); } // Function to check if the number is prime or not // using Wilson Primality Test static bool IsPrime(long p) { if (p == 4 || p <= 1) return false; // (p - 1)! ≡ (p - 1) mod p long a = Fact((int)(p - 1)) % p; if (a == p - 1) return true; return false; } static void Main(string[] args) { string s = "This is a python programming language"; string[] words = s.Split(" "); foreach(string word in words) { if (IsPrime(word.Length)) { Console.WriteLine(word); } } }}// This code is contributed by user_dtewbxkn77n |
Javascript
// JavaScript Implementation for the above approach// Function to calculate the factorialfunction fact(p) { if (p <= 1) { return 1; } return p * fact(p - 1);}// Function to check if the// number is prime or not// using Wilson Primality Testfunction isPrime(p) { if (p == 4 || p <= 1) { return false; } // (p - 1) ! ≡ (p-1) mod p let a = fact(p - 1) % p; if (a == p - 1) { return true; } return false;}let s = "This is a python programming language";let words = s.split(' ');for (let i = 0; i < words.length; i++) { if (isPrime(words[i].length)) { console.log(words[i]); }}// This code is contributed by Susobhan Akhuli. |
Output
is programming
Time complexity: O(N*K), where N is the length of the sentence and K is the length of the biggest word in the string.
Auxiliary Space: O(K)
Approach 5:
Step 1: First split the sentence into words using repeated iteration of getline() function.
Step 2: In each iteration, we check if the length of the word is prime or not using Fermat Method.
Step 3: If it is prime, then we print the word.
C++
// C++ to print words with prime length from a sentence// using Fermat Method#include <bits/stdc++.h>using namespace std;/* Iterative Function to calculate (a^n)%p in O(logy) */int power(int a, unsigned int n, int p){ int res = 1; // Initialize result a = a % p; // Update 'a' if 'a' >= p while (n > 0) { // If n is odd, multiply 'a' with result if (n & 1) res = (res * a) % p; // n must be even now n = n >> 1; // n = n/2 a = (a * a) % p; } return res;}/*Recursive function to calculate gcd of 2 numbers*/int gcd(int a, int b){ if (a < b) return gcd(b, a); else if (a % b == 0) return b; else return gcd(b, a % b);}// Function to check if the// number is prime or not// using Fermat Methodbool isPrime(unsigned int n){ int k = 3; // Corner cases if (n <= 1 || n == 4) return false; if (n <= 3) return true; // Try k times while (k > 0) { // Pick a random number in [2..n-2] // Above corner cases make sure that n > 4 int a = 2 + rand() % (n - 4); // Checking if a and n are co-prime if (gcd(n, a) != 1) return false; // Fermat's little theorem if (power(a, n - 1, n) != 1) return false; k--; } return true;}int main(){ string s = "This is a python programming language"; string word; istringstream iss(s); while (getline(iss, word, ' ')) { if (isPrime(word.length())) cout << word << endl; } return 0;}// This code is contributed by Susobhan Akhuli |
Java
// Java to print words with prime length from a sentence// using Fermat Methodimport java.util.Random;public class GFG { /* Iterative Function to calculate (a^n)%p in O(logy) */ static int power(int a, int n, int p) { int res = 1; // Initialize result a = a % p; // Update 'a' if 'a' >= p while (n > 0) { // If n is odd, multiply 'a' with result if ((n & 1) != 0) res = (res * a) % p; // n must be even now n = n >> 1; // n = n/2 a = (a * a) % p; } return res; } /* Recursive function to calculate gcd of 2 numbers */ static int gcd(int a, int b) { if (a < b) return gcd(b, a); else if (a % b == 0) return b; else return gcd(b, a % b); } // Function to check if the // number is prime or not // using Fermat Method static boolean isPrime(int n) { int k = 3; // Corner cases if (n <= 1 || n == 4) return false; if (n <= 3) return true; // Try k times while (k > 0) { // Pick a random number in [2..n-2] // Above corner cases make sure that n > 4 Random rand = new Random(); int a = 2 + rand.nextInt(n - 4); // Checking if a and n are co-prime if (gcd(n, a) != 1) return false; // Fermat's little theorem if (power(a, n - 1, n) != 1) return false; k--; } return true; } public static void main(String[] args) { String s = "This is a python programming language"; String word; String[] words = s.split(" "); for (String w : words) { if (isPrime(w.length())) System.out.println(w); } }} |
Python3
# Python to print words with prime length from a sentence# using Fermat Methodimport random# Function to calculate (a^n)%p iterativelydef power(a, n, p): res = 1 # Initialize result a = a % p # Update 'a' if 'a' >= p while n > 0: # If n is odd, multiply 'a' with result if n & 1: res = (res * a) % p # n must be even now n = n >> 1 # n = n/2 a = (a * a) % p return res# Recursive function to calculate gcd of two numbersdef gcd(a, b): if a < b: return gcd(b, a) elif a % b == 0: return b else: return gcd(b, a % b)# Function to check if a number is prime using the Fermat methoddef isPrime(n): k = 3 # Corner cases if n <= 1 or n == 4: return False if n <= 3: return True # Try k times while k > 0: # Pick a random number in [2..n-2] # Above corner cases make sure that n > 4 a = random.randint(2, n - 2) # Checking if a and n are co-prime if gcd(n, a) != 1: return False # Fermat's little theorem if power(a, n - 1, n) != 1: return False k -= 1 return Truedef main(): s = "This is a python programming language" words = s.split() for word in words: if isPrime(len(word)): print(word)if __name__ == "__main__": main()# This code is contributed by Veena mishra |
C#
// C# to print words with prime length from a sentence// using Fermat Methodusing System;using System.IO;class GFG{ // Iterative Function to calculate (a^n)%p in O(log n) static int Power(int a, int n, int p) { int res = 1; // Initialize result a = a % p; // Update 'a' if 'a' >= p while (n > 0) { // If n is odd, multiply 'a' with result if (n % 2 == 1) res = (res * a) % p; // n must be even now n = n >> 1; // n = n/2 a = (a * a) % p; } return res; } // Recursive function to calculate gcd of 2 numbers static int GCD(int a, int b) { if (a < b) return GCD(b, a); else if (a % b == 0) return b; else return GCD(b, a % b); } // Function to check if the number is prime or not using Fermat Method static bool IsPrime(int n) { int k = 3; // Corner cases if (n <= 1 || n == 4) return false; if (n <= 3) return true; // Try k times while (k > 0) { // Pick a random number in [2..n-2] // Above corner cases make sure that n > 4 Random random = new Random(); int a = random.Next(2, n - 1); // Checking if a and n are co-prime if (GCD(n, a) != 1) return false; // Fermat's little theorem if (Power(a, n - 1, n) != 1) return false; k--; } return true; }//Driver code static void Main() { string s = "This is a python programming language"; string[] words = s.Split(' '); foreach (string word in words) { if (IsPrime(word.Length)) Console.WriteLine(word); } }} |
Javascript
// Function to calculate (a^n)%p iterativelyfunction power(a, n, p) { let res = 1; // Initialize result a = a % p; // Update 'a' if 'a' >= p while (n > 0) { // If n is odd, multiply 'a' with result if (n & 1) { res = (res * a) % p; } // n must be even now n = n >> 1; // n = n/2 a = (a * a) % p; } return res;}// Recursive function to calculate gcd of two numbersfunction gcd(a, b) { if (a < b) { return gcd(b, a); } else if (a % b === 0) { return b; } else { return gcd(b, a % b); }}// Function to check if a number is prime using the Fermat methodfunction isPrime(n) { const k = 3; // Corner cases if (n <= 1 || n === 4) { return false; } if (n <= 3) { return true; } // Try k times let kCopy = k; while (kCopy > 0) { // Pick a random number in [2..n-2] // Above corner cases make sure that n > 4 const a = Math.floor(Math.random() * (n - 3)) + 2; // Checking if a and n are co-prime if (gcd(n, a) !== 1) { return false; } // Fermat's little theorem if (power(a, n - 1, n) !== 1) { return false; } kCopy--; } return true;} const s = "This is a python programming language"; const words = s.split(" "); for (const word of words) { if (isPrime(word.length)) { console.log(word); } } |
Output
is programming
Time complexity: O(k Log n). Note that the power function takes O(Log n) time.
Auxiliary Space: O(1)
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!
