Generování prvočísel (C) Vyřešeno

[flushed]

Zdravím, pokouším se napsat program, který by mi vypsal prvočísla do určitého čísla, např. když zadám max 100, vypíše mi je až do stovky. Ale ten program pořád nějak nechce fungovat... Nedávno jsem začal, tak se mi nevysmějte .

Kód: Vybrat vše

#include <stdio.h>
#include <windows.h>
#include <math.h>

#define MAX 100
int main()
{
   int i, x, k, del;

   x = 3;
   
   for(i == 0; i < MAX; i++)
   {
      del = x;
      while(del > 1 || k != 0)
      {
         del--;
         k = x % del;
      }
      if(k != 0)
      {
         printf("%d\n", x);
      }
      x++;
   }
   printf("\n");
   system("PAUSE");
   return 0;
}


[Reklama]

[faraon]

1. Vykašli se na windows.h, jednak ho v Linuxu nemám a tak je tvůj program totálně nepřenositelný (právě kvůli přenositelnosti na různé počítače a různé operační systémy jazyk C vznikl), druhak tvůj příkaz system("PAUSE") nejdřív spustí CMD.EXE a od něj požaduje provedení DOSového příkazu PAUSE, což spotřebuje minimálně miliardu tiků procesoru jen na rozběh a k tomu sežere několik megabajtů paměti!!! To je u programu velkého jen tři kilobajty hodně velký luxus, nemyslíš?
Prostě tam dej getchar() ze standardní knihovny a čekej na stisk Enteru, to sebere pár bajtů a vykoná se okamžitě.
Totéž platí pro math.h, hádám že jsi měl původně v plánu použít nějakou vyšší matematickou operaci, ale takhle je tam inludovaná zbytečně.

2. Zapni si ve vývojovém prostředí zobrazování warningů, já kompiluji přímo v konzoli příkazem gcc -pedantic -Wall pokus.c, takže jsem okamžitě dostal hlášku pokus.c:12: warning: statement with no effect. A co najdeme na řádku 12?
for(i == 0; i < MAX; i++)
Tak mě se stává spíš opačný případ, že místo porovnání přiřadím, bacha na to že v C je obrovský rozdíl mezi = a ==. V inicializaci fakt nemá smysl porovnávat, leda že bys logický výsledek toho výrazu uložil do nějaké proměnné pro další použití, takže tady bude úplně stačit jednoduché rovnítko.
Ale tady zase vidíš že Céčko si nechá bez keců líbit téměř cokoliv, a záleží jedině na programátorovi jestli si ohlídá svoje chyby. Jeden špatný šmik břitvou, a nos je pryč

3. Katastrofální chyba je, že testuješ proměnnou k ještě předtím než jí přiřadíš jakoukoliv hodnotu, takže může obsahovat jakékoliv číslo: while(del > 1 && k != 0)! Tohle by šlo použít, pokud bys programoval ruskou ruletu, která při každém spuštění dá jiný výsledek bez ohledu na stále stejné vstupní parametry

4. Ten tvůj algoritmus jsem moc nepochopil (a nerozchodil), ale řekl bych že v k = x % del zjišťuješ jestli je číslo dělitelné se zbytkem nebo beze zbytku. A bereš to zhora dolů! Zamysli se nad tím trochu, kolik čísel do stovky bude dělitelných třeba osmačtyřiceti, a kolik dvojkou? Když nejdřív prověříš ty pravděpodobnější případy, program se může dost urychlit, v tomhle případě bych tipnul že možná i stokrát.

5. Prvočísla začínají od dvojky, 0 a 1 se mezi ně nepočítají, takže hlavní smyčku můžeš s klidem udělat for (i=2;i<MAX;++i). Navíc se mi zdá že bys v tom tvém programu zjišťoval prvočísla v rozsahu 3..103, podle toho x = 3 na začátku, to by moc neodpovídalo požadovanému zadání.
Zkus to vymyslet trochu jinak, pomocí dvou vnořených smyček for() počítajících od dvojky, a nebudeš k tomu muset použít ani žádné další proměnné kromě těch dvou řídících...

[flushed]

chyb jak much . Díky moc za rady, třeba to o windows.h jsem vůbec nevěděl, a že pause je tak náročné by mě v životě nenapadlo . A o té paměti to platí jenom u PAUSE nebo i u ostatních příkazů z windows.h? Jako například system("cls");, protože pro tuhle funkci alternativu neznám..

Já právě myslel, že když napíšu, že 'k' se nesmí rovnat nule, a pak ji definuju, tak že by v tom neměl být problém...
Ohledně toho 12. řádku, původně jsem tam měl 'i = 0', ale pak jsem se to tolikrát pokoušel zprovoznit, že jsem změnil i to, co bylo správně .
A ohledně dělení čísla od vrchu.. já myslel že je to jedno jestli to beru odvrchu nebo odspodu , protože buď bude mít počítač víc práce na konci, nebo na začátku, ale ve výsledku stejně práce.

Napsal jsem ještě jeden program. Uživatel zadá číslo, a program mu řekne, jestli je to prvočíslo nebo ne.

Kód: Vybrat vše

#include <stdio.h>
#include <windows.h>
#include <conio.h>
int main()
{
  int x, k, del, i;
 
  while (1)
  {   
    printf("Zadejte cislo: ");
    scanf("%d", &x);
   
    del = x;
    i = 0;
    while (del > 0)
    {
      k = x % del;
      if (k == 0) {
        i++;
      }
      del--;
    }
    printf("\n");
   
    if (i == 2) {
      printf("PRVOCISLO");
    }
    getch();
    system("cls");
  }
  return 0;
}


Tenhle šlape jak má, ale zase jedu od konce, protože od začátku mi to nějak nejede .

[faraon]

Ano, platí to při každém použití system(), protože tímhle příkazem se právě spouští ten příkazový interpret cmd. V mém systému se spouští bash, což je něco podobného jako cmd, akorát s asi milionkrát většími možnostmi
A navíc příkaz system() je součástí standardních knihoven, já ho tady mám ve stdlib.h!
Tentokrát jsem narazil zase na conio.h, kterou používáš pro to getch(), to já tu sice mám v knihovně curses.h, ale pro přenostitelnost programu bys musel použít podmíněný překlad a podle toho na jakém systému se bude kompilovat, inkludovat správnou knihovnu. Fakt nevystačíš s tím getchar()?

1. Za hlášením PRVOCISLO ti chybí odřádkování \n, a naopak tam máš zbytečně printf("\n") o dva řádky dřív. To by dělalo paseku při dalším vývoji programu. Když potřebuješ vypsat jen jeden znak, například to \n, použij spíš funkci putchar('\n'), ta je mnohem rychlejší než složitý printf() se spoustou možností.

2. Také by se hodilo testovat jestli proběhl scanf() v pořádku, omylem jsem místo 9 stiskl * a program se mi zase zacyklil. Většina funkcí dává nějakou návratovou hodnotu, je nutné je vždy testovat a další činnost programu podle nich přizpůsobit.

3. Místo toho while (1) udělej smyčku for (x=1;x<MAX;++x), vyhoď to načítání a místo výpisu hlášení dej výpis toho aktuálního čísla, a budeš mít ten program, co jsi chtěl napsat původně

Kód: Vybrat vše

#include <stdio.h>

#define MAX 100

int main()
{
  int x, k, del, i;
 
  for (x=1;x<MAX;++x)
  {   
   
    del = x;
    i = 0;
    while (del > 0)
    {
      k = x % del;
      if (k == 0) {
        i++;
      }
      del--;
    }
   
    if (i == 2) {
      printf("%d\n",x);
    }
  }
  return 0;
}


A ještě pro porovnání, jak bych to spáchal já:

Kód: Vybrat vše

#include <stdio.h>

#define MAX 100
int main()
    {
    int i,j;

    for (i=2;i<MAX;++i)
        {
        for (j=2;j<i;++j)
            if (i%j==0)
               break;
        if (i==j)
           printf("%d\n",i);
        }

    return 0;
    }


[flushed]

To tvoje je vážně o dost jednodušší.
Právěže jsem tam dal to getch() kvůli tomu, že getchar() nečekalo, až cokoliv stisknu, ale rovnou pokračovalo dál, kdežto getch() fungovalo v pohodě.
A ještě bych se zeptal, je rozdíl mezi x++ a ++x?

[CZechBoY]

x++ zvýší číslo o 1 až po vykonání akce, ++x zvýší nejdřív číslo a pak vykoná akci
např:
x=0;
std::cout x++; //vypíše 0, v x bude 1
x=0;
std::cout ++x; //vypíše 1, v x bude 1

[flushed]

díky :) a tu náhradu za system("cls"); někdo nevíte? Když to teda nefunguje na linuxu..

[faraon]

To getchar() nečekalo, protože ti v bufferu zbyla část řetězce po zadání čísla uživatelem, ukončená znakem \n, kterou to načetlo. Buď bys musel vyprázdnit buffer (složitejší, ale správnější možnost), a nebo tam dát dvě getchar() za sebou (jednodušší, zatím s tím jako začátečník vystačíš).

Příkaz system("cls") u mě funguje, ale bash provede akorát výpis chybového hlášení, protože nezná cls. Já bych tu musel napsat system("clear"). Ale s tím plýtváním výkonu a paměti platí totéž co u tebe. Prostě je to mytí okna v přízemí z vysunutého hasičského žebříku!
Programovací jazyk je jako Lego, z malých kostiček si vytváříš větší celky, a z těch buduješ svůj program. Céčko má ty kostičky hodně malé (proti třeba Javě), ale zase jsou mnohem variabilnější - dokázal bys postavit víc kombinací z jednotlivých atomů celé periodické tabulky, nebo několika základních molekul? Ale na druhou stranu je to v Céčku pracnější, a je potřeba toho mnohem víc umět, javovským kódovacím opicím stačí vygooglit si správnou třídu nebo metodu a tu tam plácnout, ale zkus se jich zeptat kolik registrů nebo paměti která část kódu potřebuje, nebo jaké bity ve kterém portu nastavuje, když cpou něco do periférií! (Co je to port?)
Ovládání vlastností obrazovky je v knihovně curses (nebo ncurses), ale její použití je dost pracné, navíc může být na různých systémech pod různým názvem. Na tu přijde čas, až si budeš potřebovat nastavovat libovolnou pozici kurzoru na obrazovce, barvy, a jiné vlastnosti textu. Zatím zkusíme použít menší kostičky, a nebudeme tam cpát obrovskou složeninu, ze kterém bysme stejně využili jen jednu malou část.

Takže nejlepší v tuhle chvíli bude udělat si vlastní funkci cls(), pro jednoduchost jako makro, čímž využiješ schopnosti preprocesoru. V programu ti pak stačí kdekoliv napsat jen cls() a preprocesor ho ve všech případech nahradí tebou zadanou sekvencí (stejně jako u toho MAX).
Už bys měl znát pár řídících znaků, jako je \n (newline), \t (tabulator) nebo \a (alarm), jeden z dalších je \f (formfeed), který by měl způsobit vymazání obrazovky a přesunutí kurzoru do levého horního rohu. Je to synonymum pro znak s ASCII kódem 12, takže ti bude stačit zadat příkaz putchar(12) nebo správněji putchar('\n').
Mě to ale v Linuxu nefunguje, tady musím použít Escape kódy, pomocí kterých se terminál ovládá. Takže trochu delší příkaz printf("\033[2J\033[H"). Obojí si na začátku programu nadefinuješ v hlavičce jako makro:

Kód: Vybrat vše

#define cls() putchar('\f') /* Windows */
/* #define cls() printf("\033[2J\033[H")  Linux */


A potom už kdekoliv v programu stačí použít jen cls(), abys to nemusel vypisovat pokaždé celé ručně. Při překladu na Linuxu stačí přehodit značky komentářů a odkrýt správný řádek. Až časem pronikneš víc do tajů preprocesoru, můžeš použít i podmíněný překlad, který to za tebe udělá automaticky.

CZechBoY: Neděs ho s C++, řekl bych že je dost zmatený ze samotného Céčka, a ještě bych to maličko rozvedl:

Kód: Vybrat vše

int main(void)
    {
    int a,b,x,y;

    a = b = 7;
    printf("%d\t%d\tpocatecni stav a b\n",a,b);

    x = ++a;   /* nejdřív inkrementuje a pak předá hodnotu */
    y = b++;   /* nejdřív předá hodnotu a pak inkrementuje */

    printf("%d\t%d\tziskane hodnoty x y\n",x,y);
    printf("%d\t%d\tkonecny stav a b\n",a,b);

    return 0;
    }


Totéž samozřejmě platí i pro dekrementaci (--), vyzkoušej si to.

Jak jsem minule psal o tom zrychlování programu, všiml sis že by to testování šlo ještě víc zkrátit? Například pro číslo 100 nemá smysl počítat 2 až 99, ale úplně bude stačit 2 až 10, což je druhá odmocnina aktuálně prověřovaného čísla. Nejmenší dělitel každého neprvočísla je totiž vždy menší nebo roven jeho druhé odmocnině!
Takže teď je čas použít tu knihovnu math.h a funkci sqrt(). Bude to trochu složitější, protože tahle funkce pracuje s čísly double, zatímco my máme int, takže budeme muset použít přetypování do správného formátu a zase zpátky:

Kód: Vybrat vše

#include <stdio.h>
#include <math.h>

#define MAX 100
#define cls() putchar('\f') /* Windows */
/* #define cls() printf("\033[2J\033[H") Linux */

int main()
    {
    int i,j,o;

    cls();
    printf("Prvocisla do %d\n",MAX);

    for (i=2;i<MAX;++i)
        {
        o=(int)sqrt((double)i);
        for (j=2;j<=o;++j)
            if (i%j==0)
               break;
        if (j>o)
           printf("%d\n",i);
        }

    return 0;
    }


A další zrychlení by nastalo, kdybys oddělil zjištění sudého čísla dvojkou, a smyčku začal až od 3 a přičítal po dvou. Program se tím sice trochu prodlouží, ale zrychlí téměř na dvojnásobek. Otázka je, jestli to má smysl. U takhle jednoduchého programu, který běží jednou pouhých pár milisekund, asi ne (teď je to dobré jen k tomu aby ses to naučil poznat a napsat), ale pokud by to měla být součást většího programu, která se bude opakovat tisíckrát za sekundu, tak to bude zatraceně znatelný rozdíl

[flushed]

Všiml jsem si, ale když jsem stěží zvládl zjistit, zda je číslo prvočíslem, do tohoto jsem se radši nepouštěl .
a u toho výrazu x = ++a; jsem si myslel, že by to jen přidalo jedna k a, zapsalo to do x, ale a by zůstalo stejné
Ještě bych rád věděl.. jak psal ChZechBoY, tak jaktože to nemáš napsané takto? cout << ++x. Místo toho stačí std:: ? Jen tak pro zajímavost

[domitea]

pro C++:

CzechBoy počítá s tím, že není naincludovný std, takže píše jen celou cestu k danému příkazu, neboli std::cout kde std je namespace (což je něco víc než třída, ale to později) a cout je daná funkce

K té inkrementaci: Ještě je += -= /= *=

[flushed]

Ok, díky :) mám sice učebnici C od Pavla Herouta, ale vždycky jak si zkouším nějaký příklad, tak mě něco napadne a nakonec skončím úplně u něčeho jiného, na co ještě nemám ty správné znalosti .

[faraon]

Protože CZechBoY to napsal v C++, což je úplně jiný jazyk, akorát se syntaxí odvozenou z C.
V Céčku je printf(), v C++ cout.
V Céčku je stdin.h, v C++ cstdio.
A není dobré to míchat, i když v C++ se dají používat Céčkové knihovny a funkce. Opačně by to nemělo jít vůbec, i když některé překladače si nechají líbit docela dost velký čurbes.
Znalosti přijdou časem, pro zvládnutí jakékoliv činnosti na velmi dobré úrovni je podle výzkumů potřeba se jí intenzivně věnovat asi 10000 hodin, a je jedno jestli je to programování, krasobruslení, nebo hra na housle.

Výraz x = ++a; je totéž co ++a, x = a;, zatímco x = a++; je totéž co x = a, a++. Ono takových drobností je v Céčku strašná spousta, protože ho vymysleli lidé co trávili dlouhé hodiny bušením do těžkopádné klávesnice elektromechanického terminálu dálnopisu, a chtěli si ušetřit práci a čas při neustálém opakování stále stejných sekvencí. Takže ++a je totéž co ve stejně starém Pascalu inc(a), akorát je na napsání potřeba třetina stisků a čtvrtina času. Stejně tak je to s = a ==, přiřazení se prostě vyskytuje častěji než porovnání, a proto je jeho zápis kratší, i když kvůli překlepům by bylo vhodnější mít tam něco jako to pascalské := převzaté z Algolu, ze kterého se i C přes několik jazyků postupně vyvinulo.

Těch zrychlujících operátorů je celá hromada, ještě víc než píše domitea, většina z nich dokáže nahradit celý výraz nebo i několik příkazů, ale nevýhodou je že znepřehledňují kód. A člověk musí přesně vědět co dělají a jak fungují, protože někdy je i dost nebezpečné je použít. Vyzkoušej si co ti udělá tohle, ať vidíš jaké šílenosti se dají v Céčku vyvádět:

Kód: Vybrat vše

    i=5,j=8;
    printf("%d\t%d\n",i,j);

    i^=j^=i^=j;
    printf("%d\t%d\n",i,j);


Je to jedno z kouzel, u kterého ti ale nikdo nezaručí že bude vždy a všude fungovat. Proto mi také slušný překladač dal při kompilaci warning, abych věděl že se možná stane něco jiného než očekávám, nebo třeba nic.