» Poradna » Programy

Matematický problém - předem děkuji za pomoc

 |   | 

Ověřte , zda-li každé sudé číslo větší než 2 a menší než 1000 lze vyjádřit jako součet dvou prvočísel.   Mám to vyřešit v pascalu - ale to je vedlejší. Nenapadá mě žádné chytré řešení.
Děkuji za pomoc.

Odpovědi na otázku

 |   | 

A jaka te napadaji hloupa reseni ?

Souhlasím  |  Nesouhlasím  |  Odpovědět
 |   | 

Jako první řešení mě napadá najít si všechny prvočísla větší než 2 a menší než 1000. A potom pro všechny čísla který se mají ověřit zkusit jestli pro ně existují dvě prvočísla který by daly ten součet (třeba úplně debilně přes dva vnořený cykly).Ideální algoritmus to asi není, ale na naprogramování je to brnkačka

Souhlasím  |  Nesouhlasím  |  Odpovědět
 |   | 

sice pěkně blbej, ale přece jenom postup: dej si do maticové konstanty M[p] prvočísla do 1000 a pak zkoušej u každýho sudýho čísla k kombinovat jejich součty - pokud bude M[i]+M[j]=k, tak máš ověřeno a jde š na další k. Kombinace dělej tak, že vezmeš M[1] a sčítáš ho postupně se všemi M[1] až M [p] (p je počet těch prvočísel v M) a tak dále: M[2] sčítáš se všemi M[2] až M[p], atd.Udělat seznam prvočísel si můžeš např. pomocí algoritmu "Erastotenovo síto" - viz např. http://www.progr.cz/Web.view.php

Souhlasím  |  Nesouhlasím  |  Odpovědět
 |   | 

jo, tohle mě taky napadlo - nevím, hledám jestli to nejde nějak líp, ale asi ne co?

Souhlasím  |  Nesouhlasím  |  Odpovědět
 |   | 

Spravne je to "Eratostenovo sito", ne ?

Souhlasím  |  Nesouhlasím  |  Odpovědět
 |   | 

Nevím jak moc "chytré" bude moje řešení, ale zkusím:
Vyrobit seznam všech prvočísel do 1000 (ať už sítem nebo jakkoliv jinak, třeba zkoumáním, zda jsou čísla 1-1000 dělitelná něčím jiným než 1 a sebou samým...)
Pak pro každé sudé číslo 2-1000 zjistit, jestli některý z rozdílů toho čísla a jednotlivých prvočísel do poloviny jeho velikosti je taky mezi prvočísly (vyhledávání v prvočíslech například půlením intervalu). Jestli u některého ze sudých čísel ani jedno ze zkoumaných prvočísel nesplnilo tento předpoklad, zkoumané číslo nelze sečíst ze dvou prvočísel a tvrzení neplatí.
 

Souhlasím  |  Nesouhlasím  |  Odpovědět
 |   | 

Další řešení: kdyz už mám vyřešeno zkoumání jestli dané číslo je prvočíslem (je dělitelný jen 1 a sebou samým), můžu místo hledání toho rozdílu v seznamu prvočísel prozkoumat přímo, jestli je to prvočíslo...

Souhlasím  |  Nesouhlasím  |  Odpovědět
 |   | 

Takže jsem to zkusil, našel jsem si svůj starý program, který zkoumal součet dělitelů daného čísla (kromě sebe sama) a použil jsem ho.
Takže: naplnil jsem si pole prvočísel do tisícovky a pro všechna sudá čísla 2-1000 jsem bral jedno prvočíslo za druhým a skončil jsem buď když jsem našel dvojici (číslo-prvočíslo) je taky prvočíslo (součet dělitelů toho rozdílu je 1) nebo když prvočíslo je větší než polovina zkoumaného čísla. V případě že se po skončení zkoumání nenašla ani jedna taková dvojice, nebylo třeba procházet zbývající čísla a předpoklad neplatí.
Prubnul jsem to do 20000 a je to hotový za prakticky zanedbatelný čas (pod 1s)... totiž skoro všechny ty sudé hodnoty se dají sečíst z více dvojic prvočísel takže nebylo zapotřebí zkoumat moc daleko (do 1000 bylo největší použité prvočíslo 47 u 556).
Tady máš pro kontrolu výstup testovacího programu.

Souhlasím  |  Nesouhlasím  |  Odpovědět
 |   | 

Děkuji, kombinací všech postupů jsem to naprogramoval a program funguje.

Souhlasím  |  Nesouhlasím  |  Odpovědět
 |   | 
 |   |  Linux AppleMAC-Safari 5.0

Vazne potrebuju pomoc

Souhlasím  |  Nesouhlasím  |  Odpovědět

Související témata: Matematický problém, Chytré řešení


Určitě si přečtěte

Evoluce stále pokračuje, lidem se do kolen vrací kost navíc

Evoluce stále pokračuje, lidem se do kolen vrací kost navíc

** O kost zvanou fabella nás evoluce připravila už před miliony let ** V posledních desetiletích se však „ztracená kost“ znovu objevuje ** Anatomové nabádají ortopedy, aby brali fabellu v potaz

Jaroslav Petr | 31

Photolemur 3: Prostě do něj přetáhnete fotky a začne se dít magie. Tedy údajně...

Photolemur 3: Prostě do něj přetáhnete fotky a začne se dít magie. Tedy údajně...

** Je lepší nabušený Photoshop, nebo program s jedním tlačítkem? ** Photolemur si myslí to druhé ** Tento fotoeditor neumí skoro nic, a přitom (skoro) všechno

Jakub Čížek | 23

Pokud Google a Huawei ukončí spolupráci, bude to prý hrozba pro celý svět

Pokud Google a Huawei ukončí spolupráci, bude to prý hrozba pro celý svět

** Huawei chce vlastní OS pro mobily i PC. Mohl by ale uspět na Západě? ** Proti firmě se mezitím postavil i Facebook ** Google ale zároveň varuje před totální blokádou

Jakub Čížek | 65



Aktuální číslo časopisu Computer

Velký test Wi-Fi mesh

Nejlepší hodinky pro všechny aktivity

Důležité aplikace na cesty

Jak streamovat video na Twitch