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

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

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

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

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

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

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

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

Např. Eratosthenovo síto

#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

#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 ;).

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!

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)

#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;
        }
    }
}

#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);
}

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:)

#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)

ja som blbo pochopil tie prispevky predtym:)

Dakujem za pomoc