liczby pierwsze student: ile jest liczb pierwszych mniejszych od 10⁹?

Blee: Dokładną czy przybliżoną? Jeżeli przybliżoną to:

	n
π(n) ≈		(gdzie π(n) oznacza liczbę liczb pierwszych nie większych niż n)
	ln n

Maciess: Do 10⁷ juz znam. Ale dalej strasznie wolno idzie. Za wolny komputer

Maciess: o kto by pomyślał https://www.wolframalpha.com/input/?i=primes+smaller+than+10^9

Mariusz: Maciess używasz sita i zliczasz ? Przesiewasz korzystając z tablicy czy listy ? Jeśli z listy to działa trochę wolniej https://pastebin.com/nYVewAB4

Filip: Mariusz moze byc napisac klase w Javie public class CountPrimeNumbersInGivenRange { private final int from, to; public CountPrimeNumbersInGivenRange(int from, int to) { if (to < from) { throw new IllegalArgumentException("Wrong input."); } this.from = from; this.to = to; } public int countPrimeNumbers() { int count = 0; for (int i = this.from; i <= this.to; i++) { if (isPrime(i)) { count++; } return count; } private boolean isPrime(int num) { if (num < 2) { return false; } for (int i = 2; i <= num / 2; i++) { if (num % i == 0) { return false; } } return true; } }

Mariusz: private boolean isPrime(int num) { boolean b = (num > 1); int max = (int)Math.sqrt(num); for(int i=2; i<=max && b;i++) b = b && (num%i)!=0; return b } Ja bym tak napisał funkcję do sprawdzania czy liczba jest pierwsza ale twoja wersja jest bardziej oszczędna jeżeli chodzi o liczbę zmiennych lokalnych Pamiętasz jak pisaliśmy strukturę do obsługi wielomianów ? Można by spróbować na jej podstawie napisać program do symbolicznego liczenia całek z funkcji wymiernych https://matematykaszkolna.pl/forum/412526.html Tutaj zapisałem moje przemyślenia co do programu do całkowania funkcji wymiernych

Min. Edukacji: odpowiedź na tak postawione pytanie jest prosta: dużo

Mariusz: using System; namespace NamespaceName { public class ClassName { public static void Main(string[] args) { int n,counter; bool[] primes; Console.WriteLine("Podaj liczbe liczb do przesiania"); int.TryParse(Console.ReadLine(),out n); primes = new bool[n+1]; Sieve(primes); counter = 0; for(int i=0;i<=n;i++) if(primes[i]) { //Console.Write("{0} ",i); counter++; } Console.WriteLine(); Console.WriteLine("Liczba liczb pierwszych : {0} ",counter); } public static void Sieve(bool[] primes) { int n = primes.Length − 1; primes[0] = false; primes[1] = false; for(int i = 2;i <= n;i++) primes[i] = true; int max = (int)Math.Sqrt(n); for(int i = 2;i <= max;i++) if(primes[i]) for(int j = i + i;j <= n;j += i) primes[j] = false; } } } Kod programu zliczającego liczby pierwsze 10⁹ mieści się jeszcze w zakresie typu int Filip czy testowałeś swój program ze względu na czas działania ?

Mariusz: Maciess: "Do 10⁷ juz znam. Ale dalej strasznie wolno idzie. Za wolny komputer" a jakiego algorytmu użyłeś ? U Sedgewicka widziałem taki cytat choć nie pamiętam dokładnie czy to on to wymyślił "Good algorithms are better than supercomputers"

Filip: nie, ale mozna dodac ... long startTime = System.nanoTime(); countPrimes(); long estimatedTime = System.nanoTime() − startTime; sout(...);

Filip: No to klasa wielomianow juz praktycznie gotowa, zalezy w jakim jezyku chcesz to napisc − proponuje c++ lub java

Maciess: @Mariusz Nie pamiętam jakiego algorytmu uzyłem 3 lata temu

Mariusz: Filip i jak ci się podobają moje przemyślenia co do całkowania funkcji wymiernych ? Tutaj miałbym problem z napisaniem układów równań dla liczników w metodzie Ostrogradskiego i dla współczynników rozkładu na sumę ułamków prostych Jeśli chodzi o wybór języka to zamiast javy wolałbym C# bo ma przeciążanie operatorów a może w C bo nie trzeba by było przepisywać funkcji i struktury C# jest dość podobny do Javy Jak nie chcesz C# to chyba klasa napisana w C++ będzie wygodniejsza w użyciu Co do pierwiastków wielomianów to skrobnąłem w C# program do ich znajdowania przez znajdowanie wartości własnych pewnej macierzy Jednak zbieżność jest dość wolna zwłaszcza dla pierwiastków wielokrotnych https://pastebin.com/7cLraBVP Możliwe że gdybym dał inny warunek stopu a także inne przesunięcie to poprawiłoby to czas działania programu bądź dokładność wyniku W przypadku całkowania funkcji wymiernych dzięki zastosowaniu metody Ostrogradskiego poprawianie tego programu do znajdowania pierwiastków wielomianu nie ma aż takiego znaczenia