資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究從句子中列印長度為素數的單詞
在這個問題中，我們需要顯示字串中所有長度為素數的單詞。問題的邏輯部分是從字串中獲取單詞並檢查其長度是否為素數。
我們可以檢查數字的長度是否可以被任何數字整除以確保它是否為素數。此外，我們將使用埃拉託斯特尼篩法和輪因子分解演算法來檢查單詞長度是否為素數。
問題陳述 - 我們給定一個字串 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
更新於: 2023-10-27
606 次檢視
廣告