क्या आप प्राइम नंबर

मुझे वर्षों से बेहतर प्राइम नंबर पहचानकर्ता खोजने की समस्या में रूचि है। मुझे एहसास है कि यह अकादमिक शोध और अध्ययन का एक बड़ा क्षेत्र है - इसमें मेरी रुचि वास्तव में मजेदार है। सी (नीचे) में, संभावित समाधान पर मेरा पहला प्रयास था।क्या आप प्राइम नंबर

मेरा सवाल है, क्या आप एक सुधार का सुझाव दे सकते हैं (नेट पर कुछ अन्य संदर्भ उद्धृत किए बिना, मैं वास्तविक सी कोड की तलाश में हूं)? मैं इससे प्राप्त करने की कोशिश कर रहा हूं, इस तरह के समाधान की प्रदर्शन जटिलता निर्धारित करने की बेहतर समझ है।

क्या मैं यह निष्कर्ष निकालने में सही हूं कि इस समाधान की जटिलता ओ (एन^2) है?

#include <stdio.h> 
#include <math.h> 

/* isprime               */ 
/* Test if each number in the list from stdin is prime.    */ 
/* Output will only print the prime numbers in the list.    */ 

int main(int argc, char* argv[]) { 

    int returnValue = 0; 
    int i; 
    int ceiling; 
    int input = 0; 
    int factorFound = 0; 

    while (scanf("%d", &input) != EOF) { 

     ceiling = (int)sqrt(input); 
     if (input == 1) { 
      factorFound = 1; 
     } 

     for (i = 2; i <= ceiling; i++) { 
      if (input % i == 0) { 
       factorFound = 1; 
      } 
     } 

     if (factorFound == 0) { 
      printf("%d\n", input); 
     } 

     factorFound = 0;  
    } 

    return returnValue; 
}

स्रोत

2010-09-25 dvanaria

यह वास्तव में है 'O (n^0.5)'। – st0le

यह वास्तव में 'ओ (एन) 'है। एल्गोरिदम 'ओ (एन^0.5) 'है लेकिन जबकि लूप इसे' ओ (एम * एन^0.5) 'या' ओ (एम)' बनाता है। – Ishtar

यह सबसे बुनियादी प्रधान संख्या जनरेटर का एक रूप है। समस्या यह है कि, जैसे एन बहुत बड़ा हो जाता है, यह एल्गोरिदम बहुत धीरे-धीरे चलता है। नीचे वर्णित एकेएस परीक्षण, साथ ही सामान्य रूप से चलनी सिद्धांत देखें। आप जो भी करने की कोशिश कर रहे हैं उसके आधार पर, मैं अलग-अलग उपयोगों के लिए अलग-अलग दृष्टिकोणों का भी उपयोग करता हूं: क्या आपको छोटे या बड़े प्राइम्स की आवश्यकता है? शायद primes या "असली" primes? एल्गोरिदम और कार्यान्वयन आवश्यकताओं के आधार पर अलग-अलग होंगे। –

for (i = 2; i <= ceiling; i++) { 
     if (input % i == 0) { 
      factorFound = 1; 
      break; 
     } 
    }

यह "समान" एल्गोरिदम की सीमाओं के भीतर बनाने और अभी भी रहने वाला पहला सुधार है। इसे देखने के लिए किसी भी गणित की आवश्यकता नहीं है।

इसके अलावा, एक बार आप देखते हैं कि input 2 से विभाज्य नहीं है, वहाँ आदि 4 के लिए जाँच करने की कोई जरूरत नहीं, 6, 8, है किसी भी सम संख्या input में बांटा गया है, तो निश्चित रूप से 2 के लिए होता है क्योंकि यह सब बिताते हैं सम संख्याएं।

यदि आप थोड़ा एल्गोरिदम के बाहर कदम उठाना चाहते हैं, तो आप Sheldon L. Cooper उस उत्तर की तरह एक लूप का उपयोग कर सकते हैं जो उसके उत्तर में प्रदान करता है।

इस तथ्य का लाभ लेता प्रधानमंत्री अन्य 2 से 3 और हर रूप n*6 + 1 या n*6 - 1 कुछ सकारात्मक पूर्णांक के लिए की है कि (यह सिर्फ उसे टिप्पणियों से मेरे कोड सही हालांकि उनके प्रयासों की बहुत सराहना कर रहे हैं की तुलना में आसान है) n। यह देखने के लिए, बस ध्यान दें कि यदि m = n*6 + 2 या m = n*6 + 4, तो n विभाज्य द्वारा 2. यदि m = n*6 + 3 तो यह द्वारा 3.

वास्तव में विभाज्य है है, हम इस आगे ले जा सकते हैं। यदि p1, p2, .., pk पहले k प्राइम हैं, तो उन सभी पूर्णांक जो उनके उत्पाद को कॉपी करते हैं, 'स्लॉट' को चिह्नित करते हैं कि सभी शेष प्राइम फिट होना चाहिए।

इसे देखने के लिए, बस k#pk तक सभी प्राइम्स का उत्पाद बनें। तो यदि gcd(k#, m) = g, gn*k# + m विभाजित करता है और इसलिए g != 1 पर यह राशि त्रिकोणीय रूप से समग्र है। इसलिए यदि आप 5# = 30 के मामले में पुनरावृति करना चाहता था, तो अपने coprime पूर्णांकों 1, 7, 11, 13, 17, 19, 23 और 29.

हैं तकनीकी रूप से, मैं अपने पिछले दावा साबित नहीं हुआ। यह और अधिक कठिन

अगर g = gcd(k#, m), तो किसी भी पूर्णांक, n, g के लिए बिताते हैं n*k# + m क्योंकि यह k# बिताते हैं तो यह भी n*k# विभाजित करना होगा नहीं है। लेकिन यह m को विभाजित करता है, इसलिए इसे योग को विभाजित करना होगा। ऊपर मैंने केवल n = 1 के लिए इसे साबित कर दिया। मेरी गलती।

इसके अलावा, मैं नोट करना चाहिए इस बात का है कि कोई भी एल्गोरिथ्म के मौलिक जटिलता से बदल रहा है, यह अभी भी हो जाएगा O (n^1/2)। यह सब कर रहा है भारी गुणांक को कम करता है जो वास्तविक अपेक्षित रन टाइम की गणना करने के लिए उपयोग किया जाता है।

स्रोत

2010-09-25 12:07:50 aaronasterling

कुल मिलाकर अच्छी पोस्ट, लेकिन इसमें कुछ त्रुटियां हैं। कोड का आपका दूसरा स्निपेट टूटा हुआ है। इसके अलावा, आपने 'n * 6 - 1' के बजाय' n * 5 - 1' लिखा है। और 'm = n * 6 + 3' हमेशा 3 से विभाजित होता है, न कि 6. –

@ शेल्डन। धन्यवाद। सभी शर्मनाक गलतियों और मुझे उन्हें ठीक करने में खुशी है। – aaronasterling

आपका कोड अभी भी गलत है। यह 'इनपुट% (i - 1) होना चाहिए। == 0' नहीं '(इनपुट - 1) '। और जबकि लूप की स्थिति बी चाहिए ई '(i-1) <= छत'। –

-2

एल्गोरिदम सुधारने का कोई तरीका नहीं है। आपके कोड को बेहतर बनाने के छोटे तरीके हो सकते हैं, लेकिन एल्गोरिदम की आधार गति (और जटिलता) नहीं।

संपादित करें: बेशक, क्योंकि उसे सभी कारकों को जानने की आवश्यकता नहीं है, सिर्फ यह एक प्रमुख संख्या है या नहीं। महान स्थान

स्रोत

2010-09-25 12:05:31

यह झूठा है। ओ ((लॉग एन)^12) प्रारंभिक परीक्षण के लिए एल्गोरिदम मौजूद हैं। Http://en.wikipedia.org/wiki/Primality_test #Fast_deterministic_tests उनमें से कुछ एल्गोरिदम अभ्यास में व्यावहारिक नहीं हो सकते हैं, लेकिन वहाँ निश्चित रूप से O (n^2) एल्गोरिदम से बेहतर हैं। – bdonlan

इस एल्गोरिदम को बेहतर बनाने का कोई तरीका नहीं है, लेकिन वह पूरे एल्गोरिदम को प्रतिस्थापित कर सकता है। मान्य है। –

एक सामान्य सुधार बाहर तोड़ पाश के लिए बदलने के लिए किया जाएगा, जब यह एक कारक पाता है: (2 खुद की जाँच के बाद)

for (i = 2; i <= ceiling && !factorFound; i++) { 
     if (input % i == 0) { 
      factorFound = 1;

एक और संभावना 2 से काउंटर बढ़ाने के लिए किया जाएगा।

स्रोत

2010-09-25 12:08:31

यहां तक कि संख्याएं (2 को छोड़कर) प्रमुख संख्या नहीं हो सकती हैं। इसलिए, एक बार जब हम जानते हैं कि संख्या भी नहीं है, तो हम केवल यह जांच सकते हैं कि विषम संख्याएं इसके कारक हैं या नहीं।

for (i = 3; i <= ceiling; i += 2) { 
     if (input % i == 0) { 
      factorFound = 1; 
      break; 
     } 
    }

स्रोत

2010-09-25 12:12:46 letronje

-1 "यहां तक कि संख्याएं प्रमुख संख्या नहीं हो सकती हैं" एक झूठी बयान है। वास्तव में एक भी प्रमुख संख्या है, अर्थात् 2. –

@ एंड्रियास: इसे – letronje

और -1 हटा दिया गया है! :) –

आपके कोड में केवल जटिलता O (sqrt (n) lg (n)) है। यदि आप मूल गणितीय परिचालन मानते हैं ओ (1) (जब तक आप bignums का उपयोग शुरू नहीं करते हैं तब तक सत्य), तो यह केवल ओ (sqrt (n)) है।

ध्यान दें कि प्रारंभिक परीक्षण तेज-से-ओ (वर्ग (एन) एलजी (एन)) समय में किया जा सकता है। This site में AKS primality test के कई कार्यान्वयन हैं, जो ओ ((लॉग एन)^12) समय में संचालित होने के लिए साबित हुए हैं।

कुछ बहुत ही तेज, संभाव्य परीक्षण भी हैं - तेज़ी से, वे कभी-कभी गलत परिणाम देते हैं। उदाहरण के लिए, Fermat primality test:

एक नंबर p हम, primality के लिए परीक्षण एक यादृच्छिक संख्या a लेने, और चाहे a^(p-1) mod p = 1 परीक्षण करना चाहते हैं को देखते हुए। यदि गलत है, p निश्चित रूप से प्रमुख नहीं है। यदि सही है, pशायद प्राइम है। a के विभिन्न यादृच्छिक मानों के साथ परीक्षण दोहराकर, झूठी सकारात्मक की संभावना को कम किया जा सकता है।

ध्यान दें कि इस विशिष्ट परीक्षण में कुछ त्रुटियां हैं - विवरण के लिए विकिपीडिया पृष्ठ देखें, और अन्य संभाव्यता प्रारंभिक परीक्षण जिन्हें आप उपयोग कर सकते हैं।

यदि आप वर्तमान दृष्टिकोण से चिपकना चाहते हैं, तो वहां कई मामूली सुधार किए जा सकते हैं जिन्हें अभी भी बनाया जा सकता है - जैसा कि अन्य ने 2 के बाद इंगित किया है, सभी और प्राइम अजीब हैं, इसलिए आप दो संभावित कारकों को छोड़ सकते हैं लूप में एक समय। जब आप एक कारक पाते हैं तो आप तत्काल भी बाहर निकल सकते हैं। हालांकि, यह आपके एल्गोरिदम के एसिम्प्टोटिक बुरे-केस व्यवहार को नहीं बदलता है, जो ओ (वर्ग (एन) एलजी (एन)) में रहता है - यह केवल सर्वोत्तम केस (ओ (एलजी (एन)) में बदलता है, और निरंतर कारक लगभग डेढ़ से कम कर देता है।

स्रोत

2010-09-25 12:12:51 bdonlan

आप एक सुधार

सुझाव दे सकते हैं ये रहा ... एल्गोरिथ्म के लिए नहीं है, लेकिन कार्यक्रम में ही :) के लिए

आप argc उपयोग करने के लिए नहीं जा रहे हैं और argv, उनसे छुटकारा पाएं
यदि मैं "चालीस" इनपुट करता हूं तो क्या होगा?scanf() == 1, नहीं != EOF
sqrt()
returnValue का मूल्य की जरूरत नहीं है कास्ट करने के लिए कोई ज़रूरत नहीं की तुलना करें, तो आप एक निरंतर लौट सकते हैं: return 0;
इसके बजाय main() समारोह अंदर कार्यक्षमता के सभी होने का, अलग जितना काम आप सोच सकते हैं उतने कार्यों में आपका प्रोग्राम।

स्रोत

2010-09-25 12:15:59 pmg

आप छोटे बहुत अधिक कोड जटिलता जोड़ने के बिना अपने एल्गोरिदम में कटौती कर सकते हैं। उदाहरण के लिए, आप अपने सत्यापन पर भी संख्याओं को छोड़ सकते हैं, और जैसे ही आपको कोई कारक मिल जाए, खोज को रोक दें।

if (input < 2 || (input != 2 && input % 2 == 0)) 
    factorFound = 1; 

if (input > 3) 
    for (i = 3; i <= ceiling && !factorFound; i += 2) 
    if (input % i == 0) 
     factorFound = 1;

जटिलता के बारे में, अगर n अपने इनपुट संख्या है, जटिलता नहीं होगा ओ (sqrt (एन)), आप सबसे sqrt मोटे तौर पर कर रहे हैं के रूप में (एन) डिवीजनों और तुलना?

स्रोत

2010-09-25 12:20:19

आपके कार्यक्रम की समय जटिलता O(n*m^0.5) है। n इनपुट में प्राइम की संख्या के साथ। और m इनपुट में सबसे बड़ा प्राइम का आकार, या MAX_INT यदि आप चाहें तो। इसलिए जटिलता को O(n) के रूप में भी लिखा जा सकता है, जिसमें जांच के लिए प्राइम्स की संख्या है।

बिग-ओ, n के साथ (आमतौर पर) इनपुट का आकार होता है, आपके मामले में यह जांचने के लिए प्राइम की संख्या होगी। यदि मैं इस सूची को दो बार बड़ा करता हूं (उदाहरण के लिए इसे डुप्लिकेट करना), तो यह (+ -) लंबे समय तक दो बार ले जाएगा, इस प्रकार O(n)।

स्रोत

2010-09-25 12:20:51 Ishtar

आपके एल्गोरिदम में प्रत्येक प्राथमिकता परीक्षण के लिए समय जटिलता O(sqrt(n)) है।

आप हमेशा इस तथ्य का उपयोग कर सकते हैं कि 2 और 3 को छोड़कर सभी प्राइम फॉर्म हैं: 6*k+1 या 6*k-1। उदाहरण के लिए:

int is_prime(int n) { 
    if (n <= 1) return 0; 
    if (n == 2 || n == 3) return 1; 
    if (n % 2 == 0 || n % 3 == 0) return 0; 
    int k; 
    for (k = 6; (k-1)*(k-1) <= n; k += 6) { 
    if (n % (k-1) == 0 || n % (k+1) == 0) return 0; 
    } 
    return 1; 
}

यह अनुकूलन एसिम्प्टोटिक जटिलता में सुधार नहीं करता है।

संपादित

यह देखते हुए कि अपने कोड में आप संख्या को बार-बार परीक्षण कर रहे हैं, तो आप अभाज्य संख्या की एक सूची पूर्व की गणना कर सकते हैं। INT_MAX (32 बिट इन्ट्स मानते हुए) के वर्ग रूट से कम या उसके बराबर केवल 47 9 2 प्राइम हैं।

इसके अलावा, यदि इनपुट संख्या अपेक्षाकृत छोटी है तो आप sieve की गणना करने का प्रयास कर सकते हैं। अपने कार्यक्रम की शुरुआत में

#define UPPER_BOUND 46340 /* floor(sqrt(INT_MAX)) */ 
#define PRIME_COUNT 4792 /* number of primes <= UPPER_BOUND */ 

int prime[PRIME_COUNT]; 
int is_prime_aux[UPPER_BOUND]; 

void fill_primes() { 
    int p, m, c = 0; 
    for (p = 2; p < UPPER_BOUND; p++) 
    is_prime_aux[p] = 1; 
    for (p = 2; p < UPPER_BOUND; p++) { 
    if (is_prime_aux[p]) { 
     prime[c++] = p; 
     for (m = p*p; m < UPPER_BOUND; m += p) 
     is_prime_aux[m] = 0; 
    } 
    } 
} 

int is_prime(int n) { 
    if (n <= 1) return 0; 
    if (n < UPPER_BOUND) return is_prime_aux[n]; 
    int i; 
    for (i = 0; i < PRIME_COUNT && prime[i]*prime[i] <= n; i++) 
    if (n % prime[i] == 0) 
     return 0; 
    return 1; 
}

कॉल fill_primes, प्रश्नों की प्रक्रिया शुरू करने से पहले:

यहाँ दोनों विचारों का एक संयोजन है। यह बहुत तेज़ चलता है।

स्रोत

2010-09-25 12:27:54

"प्रत्येक प्रारंभिक परीक्षण के लिए समय जटिलता ओ (वर्ग (एन)) है" - लगभग नहीं! परीक्षण प्रभाग (ओपी का एल्गोरिदम) धीमा है (लॉगरिदमिक कारकों तक), लेकिन एपीआर या एकेएस तेजी से असम्बद्ध रूप से हैं। – Charles

@ चार्ल्स, हुह? मैं स्पष्ट रूप से ओपी के एल्गोरिदम का जिक्र कर रहा था ... –

क्या आप इसे संपादित करेंगे? – Charles

यहां मेरा एल्गोरिदम है, जटिलता O(n^0.5) बनी हुई है लेकिन मैं कोड में कुछ महंगे संचालन को हटाने में कामयाब रहा ...

एल्गोरिथ्म के सबसे धीमी हिस्सा है, modulus ऑपरेशन है मैं sqrt को खत्म करने या प्रबंधित i * i <= n

इस तरह मैं कीमती चक्र को बचाने ... कर देंगे तो उसका तथ्य पर आधारित है कि sum of odd numbers is always a perfect square.

के बाद से हम कर रहे हैं वैसे भी odd numbers से अधिक पुनरावृत्ति, इसका फायदा क्यों नहीं उठाते? :)

int isPrime(int n) 
{ 
    int squares = 1; 
    int odd = 3; 

    if(((n & 1) == 0) || (n < 9)) return (n == 2) || ((n > 1) && (n & 1)); 
    else 
    { 
     for(;squares <= n; odd += 2) 
     { 
      if(n % odd == 0) 
       return 0; 
      squares+=odd; 
     } 
     return 1; 
    } 
}

स्रोत

2010-09-25 13:03:22 st0le

#include <stdio.h> 
#include <math.h> 

int IsPrime (int n) { 
    int i, sqrtN; 
    if (n < 2) { return 0; } /* 1, 0, and negatives are nonprime */ 
    if (n == 2) { return 2; } 
    if ((n % 2) == 0) { return 0; } /* Check for even numbers */ 
    sqrtN = sqrt((double)n)+1; /* We don't need to search all the way up to n */ 
    for (i = 3; i < sqrtN; i += 2) { 
    if (n % i == 0) { return 0; } /* Stop, because we found a factor! */ 
    } 
    return n; 
} 

int main() 
{ 
    int n; 
    printf("Enter a positive integer: "); 
    scanf("%d",&n); 
    if(IsPrime(n)) 
    printf("%d is a prime number.",n); 
    else 
    printf("%d is not a prime number.",n); 
    return 0; 
}

स्रोत

2014-05-12 10:45:36 Dinesh

क्या आप प्राइम नंबर

उत्तर

संबंधित मुद्दे