Thuật toán tối ưu về tìm số nguyên tố

[huyentrang]

đây là code của mình. có cách nào để tối ưu về thuật toán khoonga?
Sàng Eratosthenes chie áp dụng cho các số <100 nên mình không sử dụng

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
int check_prime(int number)
{
	int i = 0;
	int temp = sqrt((float)number);
	for (i = 2;i <= temp;i++)
		if (number%i == 0)
			return 1;
			return 0;
}
int main()
{
	int number_testcase, m, n;
	int i = 0, j = 0;
	scanf_s("%d", &number_testcase);
	for (i = 0;i < number_testcase;i++)
	{
		scanf_s("%d", &m);
		scanf_s("%d", &n);
		if (m < 2)
			m = 2;
		for (j = m;j <= n;j++)
		{
			if (j % 2 == 0 && j > 2) continue;
			if (check_prime(j) == 0)
				printf("%d \n", j);
		}
		printf("\n");
	}
	system("pause");
	return 0;

}

[Phong_Ky_Vo (Tao Không Ngu.)]

Hi huyentrang.

if(huyentrang.Sex != Sex.GIRL) {
    return 0;
}
ConnectFacebook("Tao Khong Ngu");
return 1;

Đùa thôi. Bạn có thể giảm một nửa bằng cách sửa bước nhảy

	for (i = 3;i <= temp;i+=2)
		if (number%i == 0)
			return 1;
			return 0;

Hoặc dùng mảng cache 100 số nguyên tố đầu tiên và kiểm tra xem n có chia hết số nào trong khoảng đó không. (đến 541).

[noz1995 (Trần Hoàn)]

Mình định làm cái sàng đến 2147483647 nhưng mà lâu quá, chờ mệt nên thôi, tặng bạn cái sàng 1 triệu
http://puu.sh/vwEay.txt

[rogp10]

Sàng Eratosthenes chie áp dụng cho các số <100 nên mình không sử dụng

Bạn dùng sàng phân đoạn + mảng bit thì tới 10^15 còn được. Chỉ một mảng tĩnh thôi.

[banhmisg9509 (Nguyễn Hùng)]

2 thuật toán hay dùng, thấy cũng đơn giản mà vừa đủ nhanh:

def is_prime(n):// kiem tra
    if n < 2:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False

    i, w = 5, 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += w
        w = 6 - w
    return True

def ESieve(limit):
    sieveBound = (limit - 1) // 2
    upperSqrt = (int(sqrt(limit)) - 1) // 2
    primes = [True] * (sieveBound + 1)

    for i in xrange(1, upperSqrt + 1):
        if primes[i]:
            for j in xrange(i * 2 * (i + 1), sieveBound + 1, 2 * i + 1):
                primes[j] = False
    ls = [2]
    for i in xrange(1, sieveBound + 1):
        if primes[i]:
            ls.append(2 * i + 1)
    return ls

[nts311 (Sơn)]

Không biết mình có code sai không mà đo thời gian chạy thuật toán sàng số nguyên tố vs thuật toán kiểm tra xem từng số có phải nguyên tố thì cái thứ 2 chạy nhanh hơn, bằng C++.

[rogp10]

Cái này phải có code mới nói được. Mà bạn new 1 lần n slot à?

[Tri_Vu (Trí Vũ)]

Trên thực tế, để kiểm tra những số rất lớn là số nguyên tố (cỡ vài trăm chữ số) thì người ta sẽ dùng phương pháp xác suất để kiểm tra như dùng kiểm tra fermat hay kiểm tra miller-rabin (bạn có thể lên google để tìm thêm nhé)

[rogp10]

“Thường dùng” thôi, có pp chính xác nữa.