Liczby pierwsze – problem ze zrozumieniem kodu

0

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ą

1

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

0

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

1

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

1

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

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

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0