Các chú ý về số nguyên tố

Số các số nguyên tố từ 1 đến n là $n / ln(n)$

Các số dưới $10^{9}$ thì 2 số liên tiếp chỉ cách nhau $≤ 320$ đơn vị

Check Số nguyên tố $O(n)$

bool isPrime[N+5];

void Sieve()
{
    for(int i = 0; i <= N;++i) 
		{
        isPrime[i] = true;
    }
    isPrime[0] = false;
    isPrime[1] = false;
    for(int i = 2; i * i <= N; ++i)
		{
         if(isPrime[i] == true)
					{
             for(int j = i * i; j <= N; j += i)
                 isPrime[j] = false;
	        }
    }
}

Phân tích một số ra ước nhỏ nhất của nó

long long isprime[N+5];
void Sieve_gcd(){
    isprime[0] = 0;
    isprime[1] = 1;

    for(int i = 2; i*i<N; i++)
		{
        if(isprime[i] == 0)
				{
            for(int j = i*i; j <=N; j+=i)
						{
                if(isprime[j] == 0)
								{
                    isprime[j] = i;
                }
            }
        }
    }
    for (int i = 2; i < N; ++i)
		{
        if (isprime[i] == 0)
				{
            isprime[i] = i;
        }
    }
}

Số các số nguyên tố từ 1 đến n là $n / ln(n)$

Sàng để phân tích thừa số nguyên tố

long long primeDiv[N+5];
void Sieve_Fac()
{
	for(int i=2; i * i <= N; i++)
	{
		if(primeDiv[i] == 0)
		{
			for(int j=i*i; j<=N; j+=i)
			{
				primeDiv[j] = i;
			}
		}
	}
	for(int i=2; i<=N; i++)
	{
		if(primeDiv[i] == 0) primeDiv[i] = i;
	}
}

Phân tích một số ra thành các thừa số nguyên tố

//map<int, int> Fac;
//vector<int> Fac(N);
while(x > 1)
{
	Fac[primeDiv[x]]++;
	x /= primeDiv[x];
}

Kiểm tra số nguyên tố nâng cao

if (n <= 1)
        return false;

    if (n == 2 || n == 3)
        return true;

    if (n % 2 == 0 || n % 3 == 0)
        return false;
    for (int i = 5; 1ll*i*i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;

    return true;

Kiểm tra số nguyên tố cực lớn

Khi số nguyên tố quá lớn không thể chạy trong O(sqrt(n)) thì ta phải giải quyết bằng cách chạy trong sàng nguyên tố áp dụng tích chất được ghi ở dòng đầu tiên

vector<long long> snt; // Chua cac so nguyen to sau khi chay sang nguyen to truoc do
bool Ok_prime(long long x)
{
	for(auto it : snt)
	{
		if(1ll * it * it > x) return true;
		if(x % it == 0) return false;
	}
	assert(false);
}