प्रोग्रामिक रूप से बड़ी संख्या में

Question

कारक करें, इसलिए मेरे पास एक बड़ी संख्या f है। यह संख्या वास्तव में 100 अंकों से अधिक लंबी है। मुझे पता है कि कारक लगभग एक ही आकार के हैं।

यदि मेरे पास संसाधन और समय सीमित है, तो मुझे किस भाषा और एल्गोरिदम का उपयोग करना चाहिए? मैं प्रतिबंधित समय में एल्गोरिदम को कोड करने के लिए समय की लंबाई शामिल कर रहा हूं।

विचार?

संपादित करें: सीमित तक, मेरा मतलब कम से कम समय में संभव है।

Answer 1

राज्य के अत्याधुनिक प्रधानमंत्री गुणन एल्गोरिथ्म quadratic sieve और है इसके वेरिएंट। 100 अंकों से बड़ी संख्या के लिए, number sieve अधिक कुशल बन जाता है।

here का ओपन-सोर्स कार्यान्वयन है। यह केवल 4 hours on a 2.2 GHz AMD Althon में दो अंकों के बराबर प्राइम में 100 अंक संख्या को कारक करने में सक्षम है।

तो एल्गोरिदम और नमूना कार्यान्वयन है। यह आपको विचार देने या शुरू करने के लिए पर्याप्त हो सकता है।

Answer 2

यह क्लाउड कंप्यूटिंग के लिए एक अच्छा अभ्यास (और संभवतः एक दुर्लभ अच्छा उदाहरण) जैसा लगता है। इसके खिलाफ समानांतर प्रसंस्करण चलाने के लिए आसान होना चाहिए। अपनी प्रत्येक प्रक्रिया में कारकों के अपने पूल को विभाजित करें।

ऐसा कुछ उपयोगी साबित हो सकता है: http://blog.controlgroup.com/2010/10/13/hadoop-and-amazon-elastic-mapreduce-analyzing-log-files/http://en.wikipedia.org/wiki/Apache_Hadoop#Hadoop_on_Amazon_EC2.2FS3_services पर अधिक जानकारी।

(पिछले महीने में, मैं कुछ इसी तरह doming मैं यहाँ क्या सुझाव दे रहा हूँ करने के लिए का एक अच्छा वीडियो प्रदर्शन देखा था - लेकिन निश्चित रूप से, अब मैं लिंक नहीं मिल रही।)

विशेष रूप से आप अगर इसे प्रोग्रामेटिक रूप से करने की आवश्यकता नहीं है, http://www.alpertron.com.ar/ECM.HTM पर एक नज़र डालें। (http://en.wikipedia.org/wiki/Quadratic_sieve से लिंक किया गया है।) पहले लिंक पर "कई मशीनों में फैक्टरिंग" के तहत नोटों पर विशेष ध्यान दें। (के रूप में स्रोत कोड उपलब्ध है, आप के रूप में अच्छी चला सकते हैं यह एक प्रोग्राम के द्वारा वितरित फैशन है, Hadoop या की तरह इस्तेमाल करते हैं।)

Answer 3

while (x < Number) { 
    if ((Number % x) == 0) { 
     cout << x << "*" << Number/x << endl; 
     ++x; 
    } 
    else ++x; 
}