FOP4:Search & Sort

Find prime numbers

A simple way to find prime numbers

#include <iostream>
using namespace std;

bool isPrime(int n)
{
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0)
            return false;
    return true;
}

int main()
{
    for (int n = 2; n <= 100; n++)
    {
        if (isPrime(n))
            cout << n << endl;
    }
    return 0;
}

sieve of Eratosthenes

A more efficienty way to find prime numbers:

#include <iostream>
using namespace std;

const int N = 100;
bool seive[N + 1];

int main() {
    for (int i = 2; i <= N; i++)
        seive[i] = true;
    for (int d = 2; d * d <= N; d++)
        if (seive[d])
            for (int n = d * d; n <= N; n += d)
                seive[n] = false;
    for (int n = 2; n <= N; n++)
        if (seive[n])
            cout << n << endl;
    return 0;
}

#include <iostream>
using namespace std;

int main()
{
    int r3 = 0, r5 = 0, r7 = 0, seive[200];
    cin >> r3 >> r5 >> r7;
    for (int i = 0; i < 200; i++)
        seive[i] = 0;
    for (int i = r3; i < 200; i = i + 3)
        seive[i]++;
    for (int i = r5; i < 200; i = i + 5)
        seive[i]++;
    for (int i = r7; i < 200; i = i + 7)
        seive[i]++;
    for (int i = 0; i < 200; i++)
        if (seive[i] == 3)
        {
            cout << i << endl;
            break;
        }
    return 0;
}

Search

Binary search

#include <iostream>
using namespace std;

int main()
{
    int cards[13] = {101, 112, 113, 206, 207, 208,
                     303, 304, 309, 311, 402, 405, 410};
    int id = -1, low = 0, high = 12;
    while (low <= high)
    {
        int middle = (low + high) / 2;
        if (cards[middle] == 112)
        {
            id = middle;
            break;
        }
        else if (cards[middle] > 112)
            high = middle - 1;
        else
            low = middle + 1;
    }
    cout << "黑桃Q在第" << id + 1 << "张" << endl; 
    return 0;
}

Insertion sort

#include <iostream>
using namespace std;

void InsertionSort(int cards[], int n)
{
    for (int i = 1; i < n; i++)
    {
        int target = cards[i], pos = 0;
        while (target > cards[pos])
            pos++;
        for (int j = i; j > pos; j--)
            cards[j] = cards[j - 1];
        cards[pos] = target;
    }
}

Selection Sort

void SelectionSort(int cards[], int n)
{
    for (int i = 0; i < n; i++)
    {
        int min = cards[i], min_id = i;
        for (int j = i + 1; j < n; j++)
            if (cards[j] < min)
            {
                min = cards[j];
                min_id = j;
            }
        cards[min_id] = cards[i];
        cards[i] = min;
    }
}

Application

int main()
{
    int cards[13] = {101, 113, 303, 206, 405, 208,
                     311, 304, 410, 309, 112, 207, 402};
    for (int i = 0; i < 13; i++)
        cout << cards[i] << " ";
    cout << endl;
    SelectionSort(cards, 13);
    for (int i = 0; i < 13; i++)
        cout << cards[i] << " ";
    cout << endl;
    return 0;
}