Đếm ký tự có mã ASCII là số nguyên tố trong C++

Cho một chuỗi chứa chữ hoa và chữ thường, nhiệm vụ là đếm số ký tự có mã ASCII là số nguyên tố.

Mã ASCII tham khảo

A-Z: 65-90 | a-z: 97-122

Ví dụ

Input - str = "Aebg" Output - count is: 2

Giải thích - 'A'(65) không nguyên tố, 'e'(101) nguyên tố, 'b'(66) không, 'g'(103) nguyên tố → 2.

Input - str = "GOXFH" Output - count is: 2

Giải thích - 'G'(71), 'O'(79) là nguyên tố.

Phương pháp tiếp cận (Sieve of Eratosthenes)

• Tạo sàng nguyên tố (Sieve) đến 257 (max ASCII)
• Duyệt chuỗi, kiểm tra prime[(int)str[i]]
• Tăng count nếu là nguyên tố

Ví dụ code C++

#include <iostream>
#include <vector>
#include <string>
using namespace std;

#define MAX_VAL 257

int countprime(string str) {
    vector<bool> prime(MAX_VAL + 1, true);
    prime[0] = prime[1] = false;
    for (int p = 2; p * p <= MAX_VAL; p++) {
        if (prime[p]) {
            for (int i = p * 2; i <= MAX_VAL; i += p)
                prime[i] = false;
        }
    }

    int result = 0;
    for (int i = 0; i < str.length(); ++i) {
        if (prime[(int)str[i]])
            result++;
    }
    return result;
}

int main() {
    string str = "tutorialspoint";
    cout << "count is: " << countprime(str);
    return 0;
}

Kết quả

count is: 1