Prvociselne delitele – .NET – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

Prvociselne delitele – .NET – Fórum – Programujte.comPrvociselne delitele – .NET – Fórum – Programujte.com

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
duro10
Newbie
6. 11. 2011   #1
-
0
-

caute

mohli by ste mi prosim povedat co je zle v tomto kode?

            long num =600851475143;
            long[] cisla=new long[100];
            long j=0;
                     

           for(long k=2;k<num;k++)
           {
               if ((num % k == 0) && (tools.jeprvocislo(k)))
               {
                   cisla[j] = k;
                   j++;                               
              }
              
                                   
           }
           if (j == 0)
               Console.WriteLine("Cislo nema ziadne prvociselne delitele");
           else
           {

               for (long i = 0; i < j; i++)
                   Console.Write(cisla[i] + " ");
           }

public static bool jeprvocislo(long cislo)
        {
           
            bool jeprvocislo = false;
          
            long [] delitele = new long[100];
           
               
                     
                for (long i = 2; i < cislo; i++)
                {
                    if (cislo % i == 0)
                    {
                        jeprvocislo = false;
                        break;
                    }
                    else
                        jeprvocislo = true;
                       
                }


                return jeprvocislo;
        }

funguje mi to pre mensie cisla,neviem ale aky daovy typ mam zvolit pre taketo vacsie,popripade kde inde moze byt problem

dakujem

Nahlásit jako SPAM
IP: 193.110.186.–
Reklama
Reklama
Petrroll0
Stálý člen
6. 11. 2011   #2
-
0
-

Co přesně znamená menší čísla? Long by měl stačit i na docela dost dlouhá čísla.

Nahlásit jako SPAM
IP: 92.62.224.–
Peter
~ Anonymní uživatel
2539 příspěvků
6. 11. 2011   #3
-
0
-

Neviem o čo ide, ale ak chceš nejaký veľký dátovy typ, tak použi decimal. Ak chceš, tak tu si popozeraj aký by bol pre teba najvhodnejší dátovy typ: http://msdn.microsoft.com/…ary/cs7y5x0x(v=vs.90).aspx

Nahlásit jako SPAM
IP: 87.197.139.–
6. 11. 2011   #4
-
0
-

Myslím, že long by měl stačit, ale zkus lépe popsat, co ti vlastně nefunguje.

Nahlásit jako SPAM
IP: 91.217.52.–
Dušan Janošík | web: djanosik.cz, @djanosik
duro10
Newbie
7. 11. 2011   #5
-
0
-

ten program mi v pohode funguje po cisla do 1 000 000 000

bolo taketo zadanie na stranke projek euler,tak ma hneva ze pre zadane cislo ktore je tych 600851475143, mi to prote nejde,spustim program a ostane mi kurzor blokat na blackscreene,ziadna chybova hlaska ale ani nic

Nahlásit jako SPAM
IP: 195.212.29.–
KIIV+42
God of flame
7. 11. 2011   #6
-
0
-

prvocisla mas napsany extremne neefektivne... pro tak velky cisla to muze trvat hodiny nebo dokonce dny, nez to skonci...

Nahlásit jako SPAM
IP: 62.168.56.–
Program vždy dělá to co naprogramujete, ne to co chcete...
duro10
Newbie
7. 11. 2011   #7
-
0
-

a ako efektivnejsie by si mi poradil prosim ta ?mna nic ine nenapadlo 

Nahlásit jako SPAM
IP: 195.212.29.–
liborb
~ Redaktor
+18
Guru
7. 11. 2011   #8
-
0
-
Nahlásit jako SPAM
IP: 78.80.52.–
KIIV+42
God of flame
7. 11. 2011   #9
-
0
-

#8 liborb
na tak velky cisla to bude sebevrazda... by to musel udelat jako bitove pole, idealne vynechat sude cisla uplne... (a i tak by potreboval idealne cca 38GB ram (a jeste 64b procesor)

mozna kombinaci ... a pro vetsi cisla uz bude muset jet pomoci brutal force... (pripadne si je ukladat)

#7 duro1
prvocisla se tu resily nedavno (kolem tydne zpet) - najdi si to

Nahlásit jako SPAM
IP: 62.168.56.–
Program vždy dělá to co naprogramujete, ne to co chcete...
liborb
~ Redaktor
+18
Guru
7. 11. 2011   #10
-
0
-

#9 KIIV
Na wiki je jenom princip způsobu, na který nemohl přijít. A pokud jde o rychlost, tak základem je přece testovat jenom lichá čísla (případě si udělat předpis poskoku o čísla - vynechávat dělitelné 3, 5, 7, ...  - podle toho, jak dlouhý mám papír, na kterém si ten předpis bude zkoušet vytvořit :)). A hlavně, pokud jde o rychlost, tak ukládat nalezená prvočísla a testovat dělitelnost jenom jimi - to je to opravdové zrychlení, na které bych těch pár bajtů obětoval ;).

Nahlásit jako SPAM
IP: 78.80.52.–
KIIV+42
God of flame
7. 11. 2011   #11
-
0
-

samozrejme ukladat ano - jenze pro tak velky cislo potrebujes 64b hodnoty a nebude jich malo - hrozi vycerpani pameti

a pro hledani jestli je prvocislo jeho zpusobem jsou optimalizace:

1# nehledat dal nez do odmocniny toho cisla!

2# pokud nahodou uklada prvocisla testovat jen delitelnost jimi!

Nahlásit jako SPAM
IP: 62.168.56.–
Program vždy dělá to co naprogramujete, ne to co chcete...
KIIV+42
God of flame
7. 11. 2011   #12
-
0
-

a kdyz se koukam na zadani tak stejne je kravina vypocitavat si ty prvocisla...

projit vsechny ty hodnoty trva priblizne 0.021s a prvocisla jsou delitele 71, 839, 1471, 6857

samozrejme bez optimalizace trva najit posledni delitel 8462696833 asi 40 sekund a pak se prochazi jeste az do konce... (to je jeste 71x tolik)

Nahlásit jako SPAM
IP: 62.168.56.–
Program vždy dělá to co naprogramujete, ne to co chcete...
Tchibo0
Návštěvník
7. 11. 2011   #13
-
0
-

#1 duro1
 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

namespace pd
{
    class Program
    {
        static ArrayList pcd = new ArrayList();
        static DateTime lasttime;

        static void Main(string[] args)
        {
            Console.WriteLine("Delitel\tPrvocislo");
            long max = 600851475143;
            lasttime = DateTime.Now;
            long maxnew = max;

            TimeSpan ts;
            if (max % 2 == 0)
                pcd.Add((long)2);
            for (long a = 3; a <= maxnew; a+=2)
            {
                maxnew = max / a;

                if (max % a == 0)
                {
                    bool pp = JePrvocislo(a);
                    if (pp)
                        pcd.Add(a);
                    Console.Write(a + "\t " + pp + "\n");
                    
                    bool ppp = JePrvocislo(maxnew);
                    Console.Write(maxnew + "\t" + ppp + "\n");
                    if (ppp)
                        pcd.Add(maxnew);
                    ts = DateTime.Now - lasttime;
                    Console.Write("V case:\t" + ts.TotalSeconds + "s\n\n");
                }
            }
            ts = DateTime.Now - lasttime;
            Console.WriteLine("Celkovy cas:\t" + ts.TotalSeconds + "s");
            Console.WriteLine("Prvocislene delitele cisla: " + max);
            pcd.Sort();
            foreach (long lpdc in pcd)
                Console.WriteLine(lpdc);
            Console.ReadKey();
        }

        public static bool JePrvocislo(long cislo)
        {
            bool sude = cislo % 2 == 0 ? true : false;
            long delta = sude ? 1 : 2;
            for (long i = sude ? 2 : 3; i * i <= cislo; i += delta)
            {
                if (cislo % i == 0)
                {
                    return false;
                }
            }
            return true;
        }
    }
}
Nahlásit jako SPAM
IP: 109.80.248.–
Tchibo
Tchibo0
Návštěvník
7. 11. 2011   #14
-
0
-

#13 Tchibo
 Jeste je potreba nahradit:

if (max % 2 == 0)
    pcd.Add((long)2);

timhle

if (max % 2 == 0)
{
    pcd.Add((long)2);
    if (JePrvocislo(max / 2))
        pcd.Add(max / 2);
}
Nahlásit jako SPAM
IP: 109.80.248.–
Tchibo
duro1
~ Anonymní uživatel
14 příspěvků
7. 11. 2011   #15
-
0
-

Jo diky za vsetky ohlasy a rady

len nechapem preco potom na tej stranke tvrdia ze tie ulohy vsetky zbehnu uplne v pohode rychlo,ked vy hovorite ze aj dobrym algoritmom to bude trvat pomerne dlho:)

Nahlásit jako SPAM
IP: 193.110.186.–
KIIV+42
God of flame
8. 11. 2011   #16
-
0
-

#15 duro1
no jestli je podle tebe 20milisekund dlouho tak uz nevim co by se dalo zrychlit... (tedy krom vyuziti vice vlaken a rychlejsiho procesoru)

Nahlásit jako SPAM
IP: 94.112.32.–
Program vždy dělá to co naprogramujete, ne to co chcete...
duro1
~ Anonymní uživatel
14 příspěvků
8. 11. 2011   #17
-
0
-

ja som blbo pochopil tie prispevky predtym:)

Dakujem za pomoc

Nahlásit jako SPAM
IP: 193.110.186.–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 47 hostů

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý