मेरे पास रैखिक समय में कारकों या प्राइम खोजने के लिए एक नया एल्गोरिदम है - इस

Question

के लिए सत्यापन की आवश्यकता है मैंने किसी दिए गए नंबर के कारकों को खोजने के लिए एक एल्गोरिदम विकसित किया है। इस प्रकार यह यह जानने में भी मदद करता है कि दिया गया नंबर एक प्रमुख संख्या है या नहीं। मुझे लगता है कि यह कारकों या प्रमुख संख्याओं को खोजने के लिए सबसे तेज़ एल्गोरिदम है।

यह एल्गोरिदम पाता है कि 5 * एन (जहां एन इनपुट संख्या है) के समय सीमा में एक देना संख्या प्रमुख है। तो मुझे उम्मीद है कि मैं इसे एक रैखिक समय एल्गोरिदम कह सकता हूं।

मैं कैसे सत्यापित कर सकता हूं कि यह सबसे तेज़ एल्गोरिदम उपलब्ध है या नहीं? क्या कोई इस मामले में मदद कर सकता है? (तेजी से GNFS और दूसरों जाना जाता है)

एल्गोरिथ्म

Input: A Number (whose factors is to be found) 
Output: The two factor of the Number. If the one of the factor found is 1 then it can be concluded that the 
Number is prime. 

Integer N, mL, mR, r; 
Integer temp1; // used for temporary data storage 
mR = mL = square root of (N); 
/*Check if perfect square*/ 
temp1 = mL * mR; 
if temp1 equals N then 
{ 
    r = 0; //answer is found 
    End; 
} 
mR = N/mL; (have the value of mL less than mR) 
r = N%mL; 
while r not equals 0 do 
{ 
    mL = mL-1; 
    r = r+ mR; 

    temp1 = r/mL; 
    mR = mR + temp1; 
    r = r%mL; 
} 
End; //mR and mL has answer 

नीचे दिया गया है प्रदान करें अपनी टिप्पणी .. न मुझे किसी भी अधिक जानकारी के लिए संपर्क करने में संकोच।

धन्यवाद, हरीश http://randomoneness.blogspot.com/2011/09/algorithm-to-find-factors-or-primes-in.html

Answer 1

"रैखिक समय" का अर्थ है समय इनपुट डेटा के लंबाई के लिए आनुपातिक: संख्या में बिट्स आप गुणनखंड की कोशिश कर रहे की संख्या, इस मामले में। आपका एल्गोरिदम रैखिक समय, या इसके करीब कुछ भी नहीं चलता है, और मुझे डर है कि यह कई मौजूदा फैक्टरिंग एल्गोरिदम की तुलना में बहुत धीमी है। (सहित, उदाहरण के लिए, GNFS।)

Answer 2

मैं अपने एल्गोरिथ्म पर बारीकी से देखा नहीं है, लेकिन अभाज्य संख्या परीक्षण आमतौर पर कर रहे हैं की तुलना में तेजी हे (एन) (जहां n इनपुट संख्या है)। उदाहरण के लिए ले लो इस सरल एक:

def isprime(n): 
    for f in range(2,int(sqrt(n))): 
     if n % f == 0: 
     return "not prime" 
    return "prime" 

यहाँ यह निर्धारित की जाती है ओ (sqrt (एन)) अगर n प्रधानमंत्री है या नहीं, बस sqrt के लिए सभी संभव कारकों ऊपर जाँच (एन) द्वारा।

Answer 3

इस मामले में इनपुट के आकार n नहीं है, लेकिन में n बिट्स की संख्या है, तो आपके एल्गोरिथ्म का चलने का समय इनपुट के आकार में घातीय है। इसे pseudo-polynomial time के रूप में जाना जाता है।