C++ 从句子中打印长度为质数的单词

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

我们可以通过将数字的长度是否能被任何数整除来确定其是否为质数。此外，我们还将使用Eratosthenes筛和轮筛法来检查单词长度是否为质数。

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

示例示例

输入：

alpha = "Welcome to the tutorialspoin";

输出

Welcome, to, the, tutorialspoin,

解释

• ‘welcome’的长度为7，是一个质数。

• ‘to’的长度为2，’the’的长度为3，它们也都是质数。

• ‘tutorialspoin’的长度为13，是一个质数。

输入

alpha = "Python java javascript"

输出结果

“”

解释 - 这个字符串不包含任何长度为素数的单词。所以，它打印出空字符串。

输入

alpha = "I am a good person";

输出

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 <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 += ' ';
   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,

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

空间复杂度 – O(N)用于存储临时字符串中的单词。

方法2

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

算法

步骤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 <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 α) {
   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,

时间复杂度 – O(NLogN) 用于找到素数。

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

方法3

此方法使用轮筛法来检查给定的数字是否为素数。

算法

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

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

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

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

步骤5 - 从5开始，在步长为6的范围内进行迭代，直到sqrt(num)。

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

步骤7 - 最后，返回false。

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

示例

#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 += ' ';
   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,

时间复杂度 – O(N*Log5N)

空间复杂度 – O(N)