01/10/2018, 09:25

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

đâ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 
", j);
		}
		printf("
");
	}
	system("pause");
	return 0;

}

Tao Không Ngu. viết 11:28 ngày 01/10/2018

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).

Trần Hoàn viết 11:33 ngày 01/10/2018

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 viết 11:33 ngày 01/10/2018

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.

Nguyễn Duy Hùng viết 11:32 ngày 01/10/2018

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

Sơn viết 11:34 ngày 01/10/2018

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 viết 11:27 ngày 01/10/2018

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

Trí Vũ viết 11:26 ngày 01/10/2018

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 viết 11:26 ngày 01/10/2018

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

Bình luận về bài viết này

Chia sẻ tin đăng đến bạn bè

Gửi Messenger

Bài liên quan

huyentrang

0 chủ đề

0 bài viết

Tác giả nổi bật