Liczby pierwsze – problem ze zrozumieniem kodu

Dostałem do analizy kod i mam pewien problem w zrozumieniu mianowicie

int main()
{
    int k;
    cin >> k;
    if (k == 1)
        cout << "Wynik:" << endl
             << "NIE" << endl;
    if (k == 2)
        cout << "Wynik:" << endl
             << "TAK" << endl;
    for (int l = 2; l < k; l++) {
        if (k % l == 0) {
            cout << "Wynik:" << endl
                 << "NIE" << endl;
            break;
        }
        if (l == (k - 1))
            cout << "Wynik:" << endl
                 << "TAK" << endl;
    }

    return 0;
}

chodzi mi o fragment

 if(l==(k-1))cout<<"Wynik:"<<endl<<"TAK"<<endl;

Jak to możliwe ze program po takim przypisaniu wie, ze dana liczba jest liczba pierwszą

Jest to mało efektywny algorytm, bo wystarczy sprawdzać do sqrt(n) żeby sprawdzić wszystkie dzielniki. Niemniej jednak, jeśli doszedłeś do n-1, to dla n > 2 zwyczajnie n-1 nie jest dzielnikiem, a jeśli wcześniej znalazłeś dzielnik to z pętli wyszedłeś breakiem

Czy mógłbyś sprawdzić czy moje rozumowanie tego porogramu jest dobre
Przypuscmy, że daje na wejście liczbe 7, program sprawdza:
7%2 !=0- false
2==6 -false
7%3 !=0 -false
3==6 - false
7%4 !=0-false
4==6-false
7%5 !=0-false
5==6-false
7%6 !=0-false
6==6 - true, wypisanie TAK

Dobrze rozumujesz. A jak znajdzie dzielnik to wypisze "NIE" i zakończy pętlę.

W naiwnych testach (opartych na division trial), najdalej Możesz pojść korzystając z faktu, że wszystkie liczby pierwsze (poza 2 i 3) są postaci 6k +- 1.
2305843009213693951 to największa liczba pierwsza Mersenne mieszcząca się w 64 - ech bitach:

#include <stdio.h>

typedef unsigned long long int ull_int;

int prime_test(ull_int n){
	if (n <= 3) return n > 1;
	else if ( (n % 2 == 0) || (n % 3 == 0) ) return 0;
	ull_int i = 5;
	while ( i * i <= n){
		if ( (n % i == 0) || ( n % (i + 2) == 0) )
			return 0;
		i += 6;
	}
	return 1;
}

int naive_prime_test(ull_int n){
	if (n <= 3) return n > 1;
	else if ( (n % 2 == 0) || (n % 3 == 0) ) return 0;
	ull_int i = 5;
	while (i * i <= n){
		if (n % i == 0) return 0;
		i += 2;
	}
	return 1;
}

int main(){
	ull_int test = 2305843009213693951L;
	printf("%d\n", prime_test(test)); // time ./a.out: 4.57s
	printf("%d\n", naive_prime_test(test)); // time ./a.out: 7.11s
	return 0;
}

EDIT: @enedil: Tak, <=3 oraz i += 2lol
https://en.wikipedia.org/wiki/Primality_test

lion137 napisał(a):

W naiwnych testach (opartych na division trial), najdalej Możesz pojść korzystając z faktu, że wszystkie liczby pierwsze (poza 2 i 3) są postaci 6k +- 1.
2305843009213693951 to największa liczba pierwsza Mersenne mieszcząca się w 64 - ech bitach:

#include <stdio.h>

typedef unsigned long long int ull_int;

int prime_test(ull_int n){
	if (n < 3) return n > 1;
	else if ( (n % 2 == 0) || (n % 3 == 0) ) return 0;
	ull_int i = 5;
	while ( i * i <= n){
		if ( (n % i == 0) || ( n % (i + 2) == 0) )
			return 0;
		i += 6;
	}
	return 1;
}

int naive_prime_test(ull_int n){
	if (n < 3) return n > 1;
	else if ( (n % 2 == 0) || (n % 3 == 0) ) return 0;
	ull_int i = 5;
	while (i * i <= n)
		if (n % i == 0) return 0;
	return 1;
}

int main(){
	ull_int test = 2305843009213693951L;
	printf("%d\n", prime_test(test)); // time ./a.out: 4.57s
	printf("%d\n", naive_prime_test(test)); // time ./a.out: ctrl-c po dwóch minutach:)
	return 0;
}

Nie żeby coś, ale nic dziwnego że nieskończona pętla nie wykona się w dwie minuty.