寻找因素的解决方案:

def divisors(integer):
    result = set()
    i = 2
    j = integer/2
    while(i <= j):
        if integer % i == 0:
            result.add(i)
            #it dont need to 
            result.add(integer//i)
        i += 1
        j = integer//i
    if len(result) > 0:
        return f"not  prime {sorted(result)}"
    else:
        return f"{integer} is prime"

—测试---- 导入的时间

start_time = time.time()
print(divisors(180180180180))
print("--- %s seconds ---" % (time.time() - start_time))

——0.06314539909362793秒——

start_time = time.time()
print(divs(180180180180180))
print("--- %s seconds ---" % (time.time() - start_time))

——1.5997519493103027秒——

start_time = time.time()
print(divisors(1827))
print("--- %s seconds ---" % (time.time() - start_time))

——0.0秒——

start_time = time.time()
print(divisors(104729))
print("--- %s seconds ---" % (time.time() - start_time))

——0.0秒——

下面的代码:

def divs(integer):
    result = set()
    i = 2
    j = integer / 2
    loops = 0
    while (i <= j):
        if integer % i == 0:
            print(f"loops:{loops}")
            return f"{integer} is not a prime"
        i += 1
        j = integer // i
        loops += 1
    print(f"loops:{loops}")
    
    return f"{integer} is prime"

——测试——

start_time = time.time()
print(divs(180180180180180180180180))
print("--- %s seconds ---" % (time.time() - start_time))

——0.0秒——

Rabin-Miller是一个标准的概率质数检验。(你运行K次，输入数字要么肯定是合数，要么可能是素数，误差概率为4-K。(经过几百次迭代，它几乎肯定会告诉你真相)

拉宾·米勒有一个非概率(确定性)的变体。

The Great Internet Mersenne Prime Search (GIMPS) which has found the world's record for largest proven prime (274,207,281 - 1 as of June 2017), uses several algorithms, but these are primes in special forms. However the GIMPS page above does include some general deterministic primality tests. They appear to indicate that which algorithm is "fastest" depends upon the size of the number to be tested. If your number fits in 64 bits then you probably shouldn't use a method intended to work on primes of several million digits.

I found this solution pretty fast but it comes with consequences, So this is called Fermat's Little Theorem. If we take any number p and put that in (1^p)-1 or (2^p)-2...(n^p)-n likewise and the number we get is divisible by p then it's a prime number. Talking about consequences, it's not 100% right solution. There are some numbers like 341(not prime) it will pass the test with (2^341)-2 but fails on (3^341)-3, so it's called a composite number. We can have two or more checks to make sure they pass all of them. There is one more kind of number which are not prime but also pass all the test case:( 561, 1729 Ramanujan taxi no etc.

好消息是:在前250亿个数字中，只有2183不符合这个要求 的情况。

#include <iostream>
#include <math.h>
using namespace std;

int isPrime(int p)
{
    int tc = pow(2, p) - 2;
    if (tc % p == 0)
    {
        cout << p << "is Prime ";
    }
    else
    {
        cout << p << "is Not Prime";
    }
    return 0;
}

int main()
{
    int p;
    cin >> p;
    isPrime(p);
    return 0;
} 

这是我一直在玩的埃拉托色尼筛子的Python实现。

def eratosthenes(maximum: int) -> list[int | None]:
    """
    Find all the prime numbers between 2 and `maximum`.

    Args:
        maximum: The maximum number to check.

    Returns:
        A list of primes between 2 and `maximum`.
    """

    if maximum < 2:
        return []

    # Discard even numbers by default.
    sequence = dict.fromkeys(range(3, maximum+1, 2), True)

    for num, is_prime in sequence.items():
        # Already filtered, let's skip it.
        if not is_prime:
            continue

        # Avoid marking the same number twice.
        for num2 in range(num ** 2, maximum+1, num):
            # Here, `num2` might contain an even number - skip it.
            if num2 in sequence:
                sequence[num2] = False

    # Re-add 2 as prime and filter out the composite numbers.
    return [2] + [num for num, is_prime in sequence.items() if is_prime]

在一台简陋的三星Galaxy A40上，该代码大约需要16秒才能输入10000000个数字。

欢迎提出建议!

这取决于您的应用程序。这里有一些注意事项:

你需要的仅仅是一些数字是否是质数的信息，你需要所有的质数达到一定的限度，还是你需要(潜在的)所有的质数? 你要处理的数字有多大?

米勒-拉宾和模拟测试只比筛选超过一定规模的数字(我相信大约在几百万左右)的速度快。在这以下，使用试除法(如果你只有几个数字)或筛子会更快。

一个非常快速的Atkin Sieve的实现是Dan Bernstein的primegen。这个筛子比埃拉托色尼的筛子更有效率。他的页面有一些基准测试信息。