home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> การเขียนโปรแกรม C

โปรแกรม C หาเลขเฉพาะ Min/Max ในอาร์เรย์

หาเลขเฉพาะที่น้อยที่สุดและมากที่สุดในอาร์เรย์ โดยใช้ Sieve of Eratosthenes สร้างตารางเลขเฉพาะถึงค่าสูงสุดในอาร์เรย์

ตัวอย่าง

arr = {10, 4, 1, 12, 13, 7, 6, 2, 27, 33}
Min prime = 2, Max prime = 13

อัลกอริทึม

  1. หาค่าสูงสุดในอาร์เรย์
  2. Sieve หาเลขเฉพาะ 1..max
  3. สแกนอาร์เรย์ หา min/max prime

โค้ดตัวอย่าง (C++)

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

void minMaxPrime(int arr[], int n) {
    int mx = *max_element(arr, arr+n);
    vector prime(mx+1, true);
    prime[0] = prime[1] = false;
    for (int p = 2; p*p <= mx; p++)
        if (prime[p])
            for (int i = p*2; i <= mx; i += p) prime[i] = false;

    int mn = INT_MAX, mxp = INT_MIN;
    for (int i = 0; i < n; i++)
        if (prime[arr[i]]) {
            mn = min(mn, arr[i]);
            mxp = max(mxp, arr[i]);
        }
    cout << "Min prime: " << mn << "\nMax prime: " << mxp << endl;
}

int main() {
    int arr[] = {10,4,1,12,13,7,6,2,27,33};
    minMaxPrime(arr, 10);
    return 0;
}

ผลลัพธ์

Min prime: 2
Max prime: 13