Liczby pierwsze i sito Eratostenesa proszę o pomoc!

0

Witam, dostałem na zadanie napisać program, który napisałem, ale nie przechodzi testów.
Bardzo proszę o pomoc w znalezieniu błędów.

Z góry dziękuję i pozdrawiam.

Napisz program do zliczania liczb pierwszych w zadanym przedziale wykorzystując Sito Eratostenesa.

Wejście
Pierwsza linia wejscia zawiera liczbe całkowita z *<1;210^9> – liczbe zapytan,
których opisy wystepuja kolejno po sobie. Opis jednego zapytania składa sie z jednej linii
zawierajacej dwie liczby naturalne a oraz b
<1;10^7>**.

Wyjście
Dla kazdego zapytania w osobnej linii wypisz jedna liczbe odpowiadajaca na pytanie
ile liczb pierwszych znajduje sie w przedziale [a, b] (łacznie z a i b).

Pamięć: 52mb

Przykład

Przykład

Dla danych wejsciowych: Poprawna odpowiedzia jest:
8
1 10 4
1 100 25
500 1000 73
2 18 7
24 28 0
1 35 11
40 71 8
301 350 8

Sprawdzarka pokazuje błąd RTE czyli:

błąd wykonania (runtime error): w czasie działania programu wystąpił błąd, który spowodował jego przerwanie. Typową przyczyną w C++ jest tzw. segmentation fault, czyli odwołanie się do niewłaściwej komórki pamięci (wyjechanie za tablicę, użycie złego wskaźnika), ale też błąd operacji arytmetycznej (dzielenie przez zero), czy nawet zakończenie programu z kodem wyjścia innym niż 0.


int main()
{
    long int a,b,z,i,k;
    long int P[10000001] ;

     for (i=2;i<=10000000;i=i+1) 
        P[i]=1;
        P[0]=0;
        P[1]=0;
        for (i=2;i<=10000000;i=i+1) 
        {
            if(P[i])
            {
             for (k=2;k*i<=10000000;k=k+1)
             P[k*i]=0;
            }
        }
     scanf ("%d",&z);   
    for (i=1;i<=z;i=i+1)
        {
        k=0;
        scanf ("%d%d",&a,&b);
        for (i=a;i<=b;i=i+1)
        k=(k+P[i]);
        printf ("%d\n",k);      
        }
        return 0;       
}
1

1!! w wewnętrznej pętli for używasz tego samego indeksu i co w zewnętrznej

  1. po co robić tablicę typu long int jeżeli przechowujesz tylko wartości 0 i 1?
  2. używaj operatora ++ zamiast i=i+1
  3. nie musisz robić sita dla wszystkich liczb <=1000000 od razu jeżeli w danych wejściowych nie ma takich dużych przedziałów
  4. używaj nazw zmiennych które sugerują co w tej zmiennej jest
  5. fatalnie zrobione wcięcia
0

W sumie robiłem coś podobnego kiedyś to mój kod. Wczytuj tylko do zmiennej size wartość górnego przedziału.


#include "stdafx.h"
#include<iostream>
#include<vector>
#include <set> 
#include <stdexcept> 

using namespace std;

set<int> pierwsze;
set<int>::iterator it;
set<int>::iterator itek;
set<int>::iterator itek_tmp;

int _tmain(int argc, _TCHAR* argv[])
{
    pierwsze.insert(2); // wykluczam na wstępie pewne liczby pierwsze przez co będę miał mniej do sprawdzania w sicie
    pierwsze.insert(3);
    pierwsze.insert(5);
    pierwsze.insert(7);
    pierwsze.insert(11);

    long long size=2000000; // górny przedział

    for (int i=13;i<size;i+=2) // skaczemy tylko po nieparzystych wartościach ponieważ parzyste nie są pierwsze
    {
        if(i%3!=0 && i%5!=0 && i%7!=0 && i%11!=0) // wykluczamy pewne często pojawiające się wielokrotności
        {
            pierwsze.insert(i);
        }
    }

    int sito;
    int mnoznik;
    int szukana=0;

    it=pierwsze.begin();

    while ( it!=pierwsze.end() )
    {
        mnoznik=2; // początkowy mnożnik
        sito=0;
        while ( sito<*(--pierwsze.end()) ) 
        {
            sito=mnoznik*(*it); // bierzemy obecną liczbę i mnożymy razy mnożnik
            itek=pierwsze.find( sito ); // teraz szukamy tej liczby
            if (itek!=pierwsze.end() )  // jeżeli iterator nie wskazuje na koniec to oznacza, że taka liczba się znajduje
                {
                    pierwsze.erase(itek); // usuwany tą liczbe
                    it=pierwsze.find(*it); // przypisujemy iteratorowi nową wartość ponieważ stara uległa zatraceniu
                }
            ++mnoznik; // zwiększamy mnożnik
        }
    ++it; // skaczemy po kolejnych elementach
    }

    long long sum=0;
    for (it=pierwsze.begin();it!=pierwsze.end();++it)
    {
        sum+=*it;// pierwotnie obliczało sume
                ++sum; // to powinno wystarczyć
    }

    cout << sum << endl;

    system("pause");
    return 0;
}

Dodam może komentarz bo nie wiem czy się połapiesz. W c++ przed kompilacją musisz podać rozmiar tablicy aby komputer mógł sobie zarezerwować dostępną pamięć. Czasem są przypadki gdy rozmiar tablicy nie jest znany i tutaj trzeba tą pamięć alokować(przydzielić dynamicznie podczas trwania programu). Jednak są już gotowe klasy kontenerowe które robią to za nas trzeba tylko umieć się tym posłużyć. Iterator jest to tak jak by wskaźnik do danego elementu. Tutaj wykorzystałem klase set która przechowywuje liczby typu int (set<int>). Dalej powinieneś się połapać.

0

Zapomniałem dodać, że mam programować tylko w języki czystym C.
Poprawiłem tablice na zwykłą int, 'i=i+1' na 'i++', ale nie rozumiem czemu błędem jest używanie tego samego indeksu 'i' w pętli wewnętrznej, skoro wartość 'i' jest tam potrzebna, proszę o wyjaśnienie mi.

1

Zaczynasz pętlę zewnętrzną, i ma wartość 2.
Zaczynasz pętlę wewnętrzną, i ma wartość 2.
Kończysz pętlę wewnętrzną, i ma wartość 100000.
Zatem pętla zewnętrzna też się kończy. Inaczej mówiąc pętla zewnętrzna wykona się tylko dla i=2.

0
test.c:20:6: warning: implicitly declaring C library function 'scanf' with type
      'int (const char *, ...)'
     scanf ("%d",&z);   
     ^
test.c:20:6: note: please include the header <stdio.h> or explicitly provide a declaration for 'scanf'
test.c:27:9: warning: implicitly declaring C library function 'printf' with type
      'int (const char *, ...)'
        printf ("%d\n",k);      
        ^
test.c:27:9: note: please include the header <stdio.h> or explicitly provide a declaration for
      'printf'
test.c:27:19: warning: conversion specifies type 'int' but the argument has type 'long' [-Wformat]
        printf ("%d\n",k);      
                 ~^    ~
                 %ld
3 warnings generated.
0

Ten problem się tutaj przwija co chwilę.
http://4programmers.net/Forum/Newbie/115762-sito_eratostenesa

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