从句子中打印长度为素数的单词

在这个问题中，我们需要显示字符串中所有长度为素数的单词。问题的逻辑部分是从字符串中获取单词并检查其长度是否为素数。

我们可以检查数字的长度是否可以被任何数字整除以确保它是否为素数。此外，我们将使用埃拉托斯特尼筛法和轮因子分解算法来检查单词长度是否为素数。

问题陈述 - 我们给定一个字符串 alpha，我们需要打印所有长度为素数的单词。

示例

Input: alpha = "Welcome to the tutorialspoin";
Output: Welcome, to, the, tutorialspoin,

解释

• 'welcome' 的长度是 7，它是素数。

• 'to' 的长度是 2，'the' 的长度是 3，它们也是素数。

• 'tutorialspoin' 的长度是 13，素数。

示例

Input: alpha = alpha = "Python java javascript"
Output: “”

解释

字符串不包含任何长度为素数的单词。因此，它打印空字符串。

示例

Input: alpha = "I am a good person";
Output: am

解释

它打印所有长度为素数的单词。

方法 1

这是解决问题的简单方法。我们将获取字符串的每个单词并检查其长度是否为素数。我们将使用循环来检查数字是否可以被 2 到 sqrt(num) 之间的任何数字整除。如果是，则该数字是非素数。否则，该数字是素数。

算法

• 步骤 1 - 在字符串末尾追加空格以处理最后一个单词，并定义 'temp' 字符串以存储单词。

• 步骤 2 - 开始遍历字符串。如果当前字符是空格，请执行以下步骤。否则，将字符追加到 'temp' 字符串。

• 步骤 3 - 执行 checkForPrime() 函数以检查单词的大小是否为素数。

• 步骤 3.1 - 在 checkForPrime() 函数中，如果 num 为 2，则返回 true。此外，如果数字为负数，则返回 false。

• 步骤 3.2 - 从 2 到 sqrt(num) 进行迭代以检查数字是否可以被任何整数整除。如果是，则返回 true。

• 步骤 4 - 如果 checkForPrime() 函数返回 true，则打印单词。

示例

#include <stdio.h>
#include <stdbool.h>
#include <math.h>
#include <string.h>

bool checkForPrime(int num) {
   if (num == 2)
      return true;
   if (num > 1) {
      // Check if the number is divisible by any number
      for (int p = 2; p < sqrt(num) + 1; p++) {
         if (num % p == 0) {
            return false;
         }
      }
      // When a number is not divisible by any number
      return true;
   } else {
      // When a number is negative
      return false;
   }
}

void findWords(char *alpha) {
   char *token = strtok(alpha, " ");
   // Traverse the string to get words
   while (token != NULL) {
      // If the size of a word is prime
      if (checkForPrime(strlen(token))) {
         printf("%s, ", token);
      }
      token = strtok(NULL, " ");
   }
}
int main() {
   char alpha[] = "Welcome to the tutorialspoin";
   printf("The words with prime length are: - ");
   findWords(alpha);
   printf("\n");
   return 0;
}

The words with prime length are: - Welcome, to, the, tutorialspoin, 

#include <bits/stdc++.h>
using namespace std;

bool checkForPrime(int num) {
   if (num == 2)
      return true;
   if (num > 1) {
      // Check if the number is divisible by any number
      for (int p = 2; p < sqrt(num) + 1; p++) {
         if (num % p == 0) {
            return false;
         }
      }
      // When a number is not divisible by any number
      return true;
   } else {
      // When a number is negative
      return false;
   }
}
void findWords(string &alpha) {
   alpha += ' ';
   string temp;
   // Traverse the string to get words
   for (int p = 0; p < alpha.length(); p++) {
      if (alpha[p] == ' ') {
         // If the size of a word is prime
         if (checkForPrime(temp.size())) {
            cout << temp << ", ";
         }
         temp = "";
      } else {
         temp += alpha[p];
      }
   }
}
int main() {
   string alpha = "Welcome to the tutorialspoin";
   cout << " The words with the prime length are : - ";
   findWords(alpha);
   return 0;
}

The words with the prime length are : - Welcome, to, the, tutorialspoin,

import java.util.ArrayList;

public class PrimeWordFinder {
   static boolean checkForPrime(int num) {
      if (num == 2)
         return true;
      if (num > 1) {
         // Check if the number is divisible by any number
         for (int p = 2; p < Math.sqrt(num) + 1; p++) {
            if (num % p == 0) {
               return false;
            }
         }
         // When a number is not divisible by any number
         return true;
      } else {
         // When a number is negative
         return false;
      }
   }

   static void findWords(String alpha) {
      String[] words = alpha.split(" ");
      // Traverse the array of words
      for (String word : words) {
         // If the size of a word is prime
         if (checkForPrime(word.length())) {
            System.out.print(word + ", ");
         }
      }
   }

   public static void main(String[] args) {
      String alpha = "Welcome to the tutorialspoin";
      System.out.print("The words with prime length are: - ");
      findWords(alpha);
      System.out.println();
   }
}

The words with prime length are: - Welcome, to, the, tutorialspoin, 

import math

def checkForPrime(num):
   if num == 2:
      return True
   if num > 1:
      # Check if the number is divisible by any number
      for p in range(2, int(math.sqrt(num)) + 1):
         if num % p == 0:
            return False
      # When a number is not divisible by any number
      return True
   else:
      # When a number is negative
      return False

def findWords(alpha):
   words = alpha.split()
   # Traverse the list of words
   for word in words:
      # If the size of a word is prime
      if checkForPrime(len(word)):
         print(word + ", ", end="")

if __name__ == "__main__":
   alpha = "Welcome to the tutorialspoin"
   print("The words with prime length are: - ", end="")
   findWords(alpha)
   print()

The words with prime length are: - Welcome, to, the, tutorialspoin, 

时间复杂度 - O(N*N)，其中 O(N) 用于遍历字符串，O(N) 用于检查字符串长度是否为素数。

空间复杂度 - O(N) 用于将单词存储在 temp 字符串中。

方法 2

此方法使用埃拉托斯特尼筛法算法在 0 到字符串长度的范围内查找所有素数。因此，我们可以从先前计算的结果中检查单词长度是否为素数。

算法

• 步骤 1 - 定义 'primeNumber' 集合以存储 0 到字符串长度范围内的所有素数。执行 sieveAlgorithm() 函数以初始化 'primeNumber' 集合。

• 步骤 1.1 - 在 sieveAlgorithm() 函数中，定义长度为 str_len + 1 的 'isPrime' 布尔数组，并将所有元素初始化为 true。

• 步骤 1.2 - 从 2 到 sqrt(num) 进行迭代。如果 isPrime[p] 为 true，则通过将数组值更新为 false 使其所有倍数都成为非素数。

• 步骤 1.3 - 将所有素数插入从 0 到字符串长度的集合中。

• 步骤 2 - 使用 istringstream 获取字符串的流并从中获取每个单词。

• 步骤 3 - 如果集合包含单词的长度，则打印单词。

示例

#include <stdio.h>
#include <string.h> // Include for memset and strlen
#include <stdlib.h>
#include <stdbool.h>

void sieveAlgorithm(int strLen, int *pmNumbers) {
   bool isPrime[strLen + 1];
   memset(isPrime, true, sizeof(isPrime));
   for (int p = 2; p * p <= strLen; p++) {
      if (isPrime[p] == true) {
         // Change the value of a multiple of p
         for (int q = p * 2; q <= strLen; q += p)
            isPrime[q] = false;
      }
   }
   // Add prime numbers to the array
   int index = 0;
   for (int p = 2; p <= strLen; p++)
      if (isPrime[p])
         pmNumbers[index++] = p;
}

void findWords(char *alpha) {
   int pmNumbers[100]; // Assuming a maximum of 100 prime numbers
   sieveAlgorithm(strlen(alpha), pmNumbers);
   char *token = strtok(alpha, " ");
   // Check the length of each word
   while (token != NULL) {
      int wordLength = strlen(token);
      for (int i = 0; pmNumbers[i] != 0; i++) {
         if (pmNumbers[i] == wordLength) {
            printf("%s, ", token);
            break;
         }
      }
      token = strtok(NULL, " ");
   }
}

int main() {
   char alpha[] = "Welcome to the tutorialspoint";
   printf("The words with prime lengths are: ");
   findWords(alpha);
   return 0;
}

The words with prime lengths are: Welcome, to, the, 

#include <bits/stdc++.h>
using namespace std;

void sieveAlgorithm(int strLen, set<int> &pmNumbers) {
   bool isPrime[strLen + 1];
   memset(isPrime, true, sizeof(isPrime));
   for (int p = 2; p * p <= strLen; p++) {
      if (isPrime[p] == true) {
         // Change the value of a multiple of p
         for (int q = p * 2; q <= strLen; q += p)
            isPrime[q] = false;
      }
   }
   // Add prime numbers in the set
   for (int p = 2; p <= strLen; p++)
      if (isPrime[p])
         pmNumbers.insert(p);
}
void findWords(string &alpha) {
   set<int> pmNumbers;
   sieveAlgorithm(alpha.size(), pmNumbers);
   istringstream stream(alpha);
   string temp;
   // Check the length of each word
   while (stream >> temp) {
      if (pmNumbers.find(temp.size()) != pmNumbers.end()) {
         cout << temp << ", ";
      }
   }
}
int main() {
   string alpha = "Welcome to the tutorialspoint";
   cout << " The words with the prime length are: ";
   findWords(alpha);
   return 0;
}

The words with the prime length are: Welcome, to, the, 

import java.util.*;

public class PrimeLengthWords {
    
   public static void sieveAlgorithm(int strLen, Set<Integer> pmNumbers) {
      boolean[] isPrime = new boolean[strLen + 1];
      Arrays.fill(isPrime, true);
       
      for (int p = 2; p * p <= strLen; p++) {
         if (isPrime[p]) {
            // Change the value of a multiple of p
            for (int q = p * 2; q <= strLen; q += p)
               isPrime[q] = false;
         }
      }
       
      // Add prime numbers to the set
      for (int p = 2; p <= strLen; p++) {
         if (isPrime[p])
            pmNumbers.add(p);
      }
   }
    
   public static void findWords(String alpha) {
      Set<Integer> pmNumbers = new HashSet<>();
      sieveAlgorithm(alpha.length(), pmNumbers);
      String[] words = alpha.split(" ");
      
      // Check the length of each word
      List<String> primeLengthWords = new ArrayList<>();
      for (String word : words) {
         if (pmNumbers.contains(word.length())) {
            primeLengthWords.add(word);
         }
      }
      System.out.println(String.join(", ", primeLengthWords));
   }
    
   public static void main(String[] args) {
      String alpha = "Welcome to the tutorialspoint";
      System.out.print("The words with prime lengths are: ");
      findWords(alpha);
   }
}	

The words with prime lengths are: Welcome, to, the

import math

def sieve_algorithm(str_len):
   is_prime = [True] * (str_len + 1)
   pm_numbers = []
   
   for p in range(2, int(math.sqrt(str_len)) + 1):
      if is_prime[p]:
         for q in range(p * 2, str_len + 1, p):
            is_prime[q] = False

   for p in range(2, str_len + 1):
      if is_prime[p]:
         pm_numbers.append(p)
   
   return pm_numbers

def find_words(alpha):
   pm_numbers = sieve_algorithm(len(alpha))
   words = alpha.split()
   result = []
    
   for word in words:
      if len(word) in pm_numbers:
         result.append(word)
    
   print("The words with the prime length are:", ", ".join(result))

if __name__ == "__main__":
   alpha = "Welcome to the tutorialspoint"
   find_words(alpha)

The words with the prime length are: Welcome, to, the

时间复杂度 - 查找素数为 O(NLogN)。

空间复杂度 - O(N) 用于将素数存储在集合中。

方法 3

此方法使用轮因子分解技术来检查给定数字是否为素数。

算法

• 步骤 1 - 开始遍历字符串。如果当前字符是空格，则检查单词长度是否为素数。否则，将当前字符追加到 temp 字符串。

• 步骤 2 - 在 checkForPrime() 函数中，如果数字小于 1，则返回 true。

• 步骤 3 - 如果数字为 2 或 3，则返回 true。

• 步骤 4 - 如果数字可以被 2 或 3 整除，则返回 true。

• 步骤 5 - 开始以 6 为步长从 5 和 sqrt(num) 进行迭代。

• 步骤 6 - 如果数字可以被 p 或 p + 2 整除，则返回 false。

• 步骤 7 - 最后，返回 false。

• 步骤 8 - 如果 checkForPrime() 函数返回 true，则打印单词。

示例

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

// Function to check if a number is prime
bool checkForPrime(int num) {
   if (num <= 1) {
      return false;
   } else if (num == 2 || num == 3) {
      return true;
   } else if (num % 2 == 0 || num % 3 == 0) {
      return false;
   } else {
      // Check divisibility by numbers of the form 6k +/- 1
      for (int p = 5; p * p <= num; p += 6) {
         if (num % p == 0 || num % (p + 2) == 0)
            return false;
      }
   }
   return true;
}

// Function to find words with prime lengths in a string
void findWords(char *alpha) {
   char temp[100]; // Assuming a maximum word length of 100
   int tempIndex = 0;
   
   for (int p = 0; alpha[p] != '\0'; p++) {
      if (alpha[p] == ' ') {
         temp[tempIndex] = '\0'; // Null-terminate the temp string
         tempIndex = 0; // Reset the index
         
         // If the size of the word is prime, print it
         if (checkForPrime(strlen(temp))) {
            printf("%s, ", temp);
         }
      } else {
         temp[tempIndex++] = alpha[p]; // Add character to temp
      }
   }
}

int main() {
   char alpha[] = "Welcome to the tutorialspoint";
   printf("The words with prime lengths are: ");
   findWords(alpha);
   return 0;
}

The words with prime lengths are: Welcome, to, the, 

#include <bits/stdc++.h>
using namespace std;

bool checkForPrime(int num){
   // When a number is less than 1
   if (num <= 1) {
      return false;
   } else if (num == 2 || num == 3) {
      return true;
   } else if (num % 2 == 0 || num % 3 == 0) {
      // Check whether the number is divisible by 2 or 3
      return false;
   } else {
      // Check whether the number is divisible by a multiple of 5 and 7
      for (int p = 5; p * p <= num; p += 6) {
         if (num % p == 0 || num % (p + 2) == 0)
            return false;
      }
   }
   return true;
}
void findWords(string &alpha) {
   alpha += ' ';
   string temp;
   // Traverse the string to get words
   for (int p = 0; p < alpha.length(); p++) {
      if (alpha[p] == ' ') {
         // If the size of the word is prime
         if (checkForPrime(temp.size())) {
            cout << temp << ", ";
         }
         temp = "";
      } else {
         temp += alpha[p];
      }
   }
}
int main() {
   string alpha = "Welcome to the tutorialspoint";
   cout << " The words with the prime length are: ";
   findWords(alpha);
   return 0;
}

The words with the prime length are:  Welcome, to, the,

public class PrimeLengthWords {
    
   // Function to check if a number is prime
   public static boolean checkForPrime(int num) {
      if (num <= 1) {
         return false;
      } else if (num == 2 || num == 3) {
         return true;
      } else if (num % 2 == 0 || num % 3 == 0) {
         return false;
      } else {
         // Check divisibility by numbers of the form 6k +/- 1
         for (int p = 5; p * p <= num; p += 6) {
            if (num % p == 0 || num % (p + 2) == 0) {
               return false;
            }
         }
      }
      return true;
   }
    
   // Function to find words with prime lengths in a string
   public static void findWords(String alpha) {
      alpha += ' ';  // Add a space to handle the last word
      String temp = "";
      String[] words = alpha.split(" ");
      System.out.print("The words with prime lengths are: ");
      for (String word : words) {
         // If the size of the word is prime, print it
         if (checkForPrime(word.length())) {
            System.out.print(word + ", ");
         }
      }
   }
    
   public static void main(String[] args) {
      String alpha = "Welcome to the tutorialspoint";
      findWords(alpha);
   }
}

The words with prime lengths are: Welcome, to, the, 

# Function to check if a number is prime
def check_for_prime(num):
   if num <= 1:
      return False
   elif num == 2 or num == 3:
      return True
   elif num % 2 == 0 or num % 3 == 0:
      return False
   else:
      # Check divisibility by numbers of the form 6k +/- 1
      p = 5
      while p * p <= num:
         if num % p == 0 or num % (p + 2) == 0:
            return False
         p += 6
   return True

# Function to find words with prime lengths in a string
def find_words(alpha):
   alpha += ' '  # Add a space to handle the last word
   temp = ''
   result = []
   for char in alpha:
      if char == ' ':
         # If the size of the word is prime, add it to the result
         if check_for_prime(len(temp)):
            result.append(temp)
         temp = ''
      else:
         temp += char
   print("The words with prime lengths are:", ", ".join(result))

if __name__ == "__main__":
   alpha = "Welcome to the tutorialspoint"
   print("The words with prime lengths are:", end=' ')
   find_words(alpha)

The words with prime lengths are: Welcome, to, the

Shubham Vora

更新于: 2023-10-27

606 次查看

开启你的 职业生涯

通过完成课程获得认证

开始