[_gabriel]

Chodzi o sprawdzenie, czy dana liczba jest liczbą pierwszą. Skąd ziomek wziął tą formułę z pierwiastkiem? Nie mogę jej nigdzie znaleźć.

var number;

Console.WriteLine("Accept number:");
number = Convert.ToInt32(Console.ReadLine());

if (IsPrime(number))
{
    Console.WriteLine("It is prime");
}
else
{
    Console.WriteLine("It is not prime");
}       

public static bool IsPrime(int number)
{
    if (number <= 1) return false;
    if (number == 2) return true;
    if (number % 2 == 0) return false;

    var boundary = (int)Math.Floor(Math.Sqrt(number));

    for (int i = 3; i <= boundary; i += 2)
        if (number % i == 0)
            return false;

    return true;        
}

#naukaprogramowania #liczbypierwsze #matematyka #pytanie

[Szymif]

@_gabriel chodzi ci o to skąd jest math.sqrt?

[XD__]

@_gabriel: Jeżeli liczba ma jakiekolwiek dzielniki (nie jest liczbą pierwszą), to największy dzielnik może być równy pierwiastkowi kwadratowemu z tej liczby.
Lepiej to widać jak sobie rozrysujesz po kolei dzielniki dla np takiego 36

[93michu93]

@_gabriel: Przy szukaniu dzielników liczb wystarczy jechać pętlą do pierwiastka kwadratowego, ponieważ każda liczba naturalna ma co najwyżej jeden dzielnik większy od swojego pierwiastka kwadratowego

[RandomowoWygenerowany]

@XD__: 36, ale propozycja, parzyste wywala na poczatku. i dlatego w petli skacze co 2. optymalizacja

[Blomex]

@XD__: prawie dobrze, tylko, że najmniejszy dzielnik.
Na przykład 2*37= 74, 74 jest pierwsze pierwiastek z 74 to poniżej 9.

[tyrytyty]

formułę

@_gabriel: wzór

[deryt]

każda liczba naturalna ma co najwyżej jeden dzielnik większy od swojego pierwiastka kwadratowego

@93michu93:
To nie jest prawda. 1024 ma cztery dzielniki: 64, 128, 256, 512 które są większe niż sqrt(1024)=32.
@_gabriel
Jeśli ma większy niż sqrt(n) to:
dzielisz n przez ten dzielnik. I ten wynik będzie liczbą która też jest dzielnikiem, a jest mniejsza niż sqrt(n). więc wystarczy sprawdzić do sqrt(n).

[XD__]

@Blomex: Tak, tak miałem napisać. Przejęzyczenie XD

[93michu93]

To nie jest prawda. 1024 ma cztery dzielniki: 64, 128, 256, 512 które są większe niż sqrt(1024)=32.

@deryt: a przepraszam, jezeli szukamy isPrime to jezeli nie znajdziemy dzielnika do pierwiastka to juz dalej tez go nie bedzie, prawda?

[deryt]

jezeli nie znajdziemy dzielnika do pierwiastka to juz dalej tez go nie bedzie, prawda?

@93michu93:
Tak, o tym mowa.