Suma liczb z zadanego przedziału, z wyłączeniem liczb pierwszych

Cześć chciałbym obliczyć tą sumę, problem pojawia się z liczbami pierwszymi...

Oblicz sumę wszystkich kolejnych liczb naturalnych od n do m, z wyłączeniem liczb pierwszych.

Przykładowo:
n-32
m-24570

Jaki jest to problem? Zdecyduj się o jaki język pytasz.

jak wyzbyć się liczb pierwszych obliczając sume ciągu?

Masz jakieś ograniczenie co do wielkości m i n? Dodatkowe ograniczenia co do użytej pamięci lub wielkości kodu źródłowego?

Odejmij je od sumy, lub ich nie dodawaj do niej.

Może w ten sposób... Mając takie cudo, jak pozbyć się niechcianych liczb pierwszych

a1=32
an=24570

#include<iostream>
using namespace std;

int main()
{
    int n;
    float a1,an,suma=0;
    cout<<"\n\n\t\t SUMA \n\n";
    cout<<"\twartosc n = ";
    cin>>n;
    cout<<"\n\n\twartosc pierwszego wyrazu ciagu: ";
    cin>>a1;
    cout<<"\n\n\twartosc " <<n<<" wyrazu ciagu: ";
    cin>>an;
    cout<<"\n\n";
    suma=(a1+an)*n/2;
    cout<<"\n\n\tSuma kolejnych "<< n<<" wyrazow ciagu arytmetycznego wynosi: "<<suma;
    cin.ignore();
    getchar();
    return 0;
    }

Możliwe, że ktoś z lepszym backgroundem matematycznym mnie poprawi, ale ja bym to zrobił tak:

• napisz sobie funkcję is_prime(), która sprawdza pierwszość liczby
• dla każdego wyrazu ciągu¹ (nie do końca rozumiem czemu wczytujesz 3 liczby od użytkownika) sprawdź czy liczba jest pierwsza i jeśli jest - odejmij ją od sumy.

¹_{Możesz skorzystać z zależności, że każda liczba pierwsza n większa od 3 spełnia n = 6 * k + 1 lub n = 6 * k - 1 dla całkowitego k}

Kod zgodny z powyższym:

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

int sum_non_primes(int start, int end){
	int s = 0;
	for (int i = start; i <= end; i++){
		if (! prime_test(i))
			s += i;
	}
	return s;
}

kq napisał(a):

Możliwe, że ktoś z lepszym backgroundem matematycznym mnie poprawi, ale ja bym to zrobił tak:

• napisz sobie funkcję is_prime(), która sprawdza pierwszość liczby
• dla każdego wyrazu ciągu¹ (nie do końca rozumiem czemu wczytujesz 3 liczby od użytkownika) sprawdź czy liczba jest pierwsza i jeśli jest - odejmij ją od sumy.

¹_{Możesz skorzystać z zależności, że każda liczba pierwsza n większa od 3 spełnia n = 6 * k + 1 lub n = 6 * k - 1 dla całkowitego k}

Twoje rozwiązanie ma dwie wady:

• zamiast sprawdzania za każdym razem przez is_prime tu aż się prosi o sito Eratostenesa;
• przy zsumowaniu najpierw a odejmowaniu potem można przekroczyć zakres -- choć w liczbach całkowitych w reprezentacji U2 i tak wynik będzie poprawny. :)

Zgadza się nasze rozwiązanie jest O(n^2), a Twoje O(n), ale też ma wady - znacząco komplikuje kod, no i zajmuje sporo pamięci.

lion137 napisał(a):

Zgadza się nasze rozwiązanie jest O(n^2), a Twoje O(n), ale też ma wady - znacząco komplikuje kod, no i zajmuje sporo pamięci.

Eratostenes chyba jest jednak trochę wolniejszy niż O(n). Dokładniej: O(n loglog n). :)

Rozwiązanie -- z niewątpliwą zaletą prostoty :) -- o złożoności O(n^2) ma zastosowanie tylko przy małych ciągach. A zwróciłem uwagę, że jako przykład @Kuba Moszkowicz podał dość duże liczby n=32 m=24570... Trzeba by przetestować, ale złożoność może mieć tu znaczenie.

"znacząco komplikuje" -- kwestia względna. Sito Eratostenesa jest obowiązkowym (w sensie programu nauczania) zagadnieniem na maturę z informatyki...