How to use the prime number judgment algorithm in C++

How to use the prime number judgment algorithm in C

Prime number judgment is a common problem in algorithms. It requires judging whether a given number is a prime number (prime number). In C, we can use different algorithms to solve this problem. This article will introduce two common prime number judgment algorithms and give corresponding code examples.

1. Brute force method (brute force method)
   Brute force method (violent method) is the most direct algorithm. Its idea is to compare a given number with all numbers less than the number. Perform the remainder operation. If there is a number that can divide the number, then the number is not a prime number, otherwise it is a prime number.

The following is an example of C code that uses brute force to determine whether a given number is prime:

#include <iostream>

bool isPrime(int n)
{
    if (n < 2)   // 小于2的数都不是素数
        return false;
        
    for (int i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
            return false;
    }
    
    return true;
}

int main()
{
    int num;
    std::cout << "请输入一个整数：";
    std::cin >> num;
    
    if (isPrime(num))
        std::cout << num << " 是素数。" << std::endl;
    else
        std::cout << num << " 不是素数。" << std::endl;
        
    return 0;
}

2. Sieve of Eratosthenes
   Era The Tostoney sieve method is a prime number judgment algorithm based on the sieve method. Its idea is to first generate a table of all numbers starting from 2 to a given range, and then sift out the non-prime numbers one by one. What is left in the end is Prime number.

The following is a C code example that uses the sieve of Eratosthenes to determine whether a given number is a prime number:

#include <iostream>
#include <vector>

bool isPrime(int n)
{
    if (n < 2)   // 小于2的数都不是素数
        return false;
        
    std::vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false;
    
    for (int i = 2; i * i <= n; i++)
    {
        if (is_prime[i])
        {
            for (int j = i * i; j <= n; j += i)
            {
                is_prime[j] = false;
            }
        }
    }
    
    return is_prime[n];
}

int main()
{
    int num;
    std::cout << "请输入一个整数：";
    std::cin >> num;
    
    if (isPrime(num))
        std::cout << num << " 是素数。" << std::endl;
    else
        std::cout << num << " 不是素数。" << std::endl;
        
    return 0;
}

The above is the C code of two common prime number determination algorithms Code example, by running this code, we can determine whether a given number is prime. Of course, both algorithms have their own advantages and disadvantages. In specific application scenarios, the appropriate algorithm needs to be selected based on the actual situation. I hope this article will be helpful to readers in understanding and using the prime number judgment algorithm in C.

The above is the detailed content of How to use the prime number judgment algorithm in C++. For more information, please follow other related articles on the PHP Chinese website!