मैंने विल्सन प्राइम नंबरों का एक कोड लिखा है और मेरा कोड अधिकांश नंबरों के लिए काम कर रहा है लेकिन यह बहुत बड़ी संख्या के लिए OverflowError: int बहुत बड़ा फ्लोट में कनवर्ट करने के लिए दे रहा है। क्या बहुत बड़ी संख्या के लिए विल्सन अभाज्य संख्या कोड लिखने का कोई तरीका है। विल्सन प्राइम विल्सन प्राइम्स की जाँच के लिए मुख्य समस्या यह है कि इसे निम्नलिखित शर्त को पूरा करना चाहिए। जहां P एक अभाज्य संख्या का प्रतिनिधित्व करता है

फिर ((P-1)! + 1) / (P * P) को एक पूर्ण संख्या देनी चाहिए। और जैसा कि आप देख सकते हैं कि इस प्रक्रिया में भाज्य शामिल हैं, इसलिए बहुत बड़ी संख्या के लिए यह काफी कठिन है।

मेरा कोड:

def am_i_wilson(n):
    import math
    n1 = math.sqrt(n)
    n1 = math.ceil(n1)
    c = 0

    def fact(n):
        num = 1
        for i in range(2,n+1):
            num = num*i
        return num

    if n <= 1:
        return False

    for i in range(2, n1 + 1):
        if n%i == 0:
            c+ = 1

    if c != 0:
        return False

    x = (fact(n-1)+1)/((n**2)*1.0)

    return x.is_integer()

मेरे कोड में, यदि नंबर विल्सन प्राइम और गलत है तो मैं सही लौट रहा हूं। यहां n नंबर है जिससे पता चलता है कि यह विल्सन प्राइम है या नहीं।

0
Rahulkumar Jha 18 सितंबर 2019, 10:19
अंत में मुझे विकिपीडिया लेख "en.wikipedia.org/wiki/Wilson_prime पढ़कर उत्तर मिल गया। ". चूंकि (5,13,563) अब तक एकमात्र विल्सन प्राइम नंबर हैं, इसलिए बाकी सभी नॉन-विल्सन प्राइम नंबर होंगे। लेकिन अगर किसी के पास कोई बेहतर तरीका है तो कृपया उसका जवाब दें।
 – 
Rahulkumar Jha
18 सितंबर 2019, 10:33

3 जवाब

मुझे लगता है कि यह सबसे कारगर तरीका है

import math
def am_i_wilson(num):
    if num < 2 or not all(n % i for i in range(2, num)):
        return False
    return (math.factorial(num - 1) + 1) % (num ** 2) == 0

या आप इसे भी आजमा सकते हैं

import math
def am_i_wilson(n):
    if n <= 2:
        return False
    fact=math.factorial(n-1)
    #this conditional checks that the number is prime or not
    #this condition is called wilson theorem in number theory
    if (fact+1)%n==0:
        x = (fact+1)%(n**2)
        if x==0:
            return True
        else:
            return False
    else:
        return False
1
Aaryan Shekhar Jha 14 पद 2019, 23:42
आपका पहला उदाहरण सबसे कुशल तरीका नहीं हो सकता है क्योंकि यह ओपी के समान अक्षम प्राइम टेस्ट को एम्बेड करता है, मॉड्यूलस टेस्ट को आवश्यकता से कहीं अधिक संख्याओं पर करता है। (2 एक विशेष मामले पर विचार करें, फिर num के वर्गमूल तक विषम संख्याओं का परीक्षण करें)। आपके दूसरे उदाहरण में, क्या (fact + 1) % n == 0 एक आवश्यक प्रारंभिक मापांक है या (fact + 1) % n ** 2 == 0 प्रश्न का उत्तर देने के लिए पर्याप्त है?
 – 
cdlane
31 पद 2019, 10:03
हाँ, मुझे अपने पहले उदाहरण के लिए आपकी बात मिल गई है और मैं इसे निश्चित रूप से ठीक कर दूंगा, और दूसरे उदाहरण के लिए शर्त (fact + 1) % n ==0 यह जांचने के लिए एक आवश्यक शर्त है कि संख्या n एक अभाज्य संख्या है या नहीं (यह शर्त दी गई थी) विल्सन द्वारा और इसलिए विल्सन प्रमेय कहा जाता है), दूसरी शर्त (fact + 1) % n ** 2 भी यह कहने के लिए पर्याप्त है कि दी गई अभाज्य संख्या विल्सन प्राइम है। तो मूल रूप से यहां दोनों स्थितियों का एक साथ उपयोग किया जाता है लेकिन स्वाभाविक रूप से उनका अलग-अलग उपयोग किया जाता है। एक का उपयोग प्रारंभिकता के परीक्षण के लिए किया जाता है और दूसरे का उपयोग विल्सन प्राइम . के परीक्षण के लिए किया जाता है
 – 
Aaryan Shekhar Jha
2 जिंदा 2020, 20:24
मेरा दूसरा मुद्दा नीचे आता है, यदि n**2, x को समान रूप से विभाजित करता है, तो क्या इसका पालन नहीं होता है कि n को x समान रूप से विभाजित करना चाहिए? उदा. (9 विभाजित n) -> (3 विभाजित n)। काउंटर उदाहरण क्या है?
 – 
cdlane
3 जिंदा 2020, 05:32

अगर किसी के पास कोई बेहतर तरीका है तो कृपया इसका उत्तर दें।

आपका प्रोग्राम मुख्य रूप से primes और कंप्यूटिंग फैक्टोरियल के परीक्षण पर निर्भर करता है। आप फैक्टोरियल लॉजिक को अलग करते हैं लेकिन एक अक्षम प्राइम टेस्ट एम्बेड करते हैं - यह जानने के बाद कि यह संख्या प्राइम नहीं है, यह शेष परीक्षण करता रहता है! मैं दोनों को अलग कर दूंगा ताकि उन्हें विल्सन प्राइम टेस्ट से स्वतंत्र रूप से परीक्षण और अनुकूलित किया जा सके:

def factorial(n):
    number = 1

    for i in range(2, n + 1):
        number *= i

    return number

def am_i_prime(n):
    if n < 2:
        return False

    if n % 2 == 0:
        return n == 2

    for divisor in range(3, int(n ** 0.5) + 1, 2):
        if n % divisor == 0:
            return False

    return True

def am_i_wilson(n):
    return am_i_prime(n) and (factorial(n - 1) + 1) % n ** 2 == 0

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

0
cdlane 19 सितंबर 2019, 08:49

मैं हाल ही में प्रमुख चलनी के साथ प्रयोग कर रहा हूं। मैंने रॉबर्ट विलियम हैंक्स द्वारा लिखित उनमें से एक में एक त्वरित संशोधन (यानी हैक) किया और इसके साथ आया। पहले आउटपुट:

$ ./wilson_primes.py 10000 [5, 13, 563]

... इसलिए मुझे संदेह है कि विल्सन प्राइम के बारे में विकिपीडिया लेख सही है ;-)

import sys
def fact(n):
    num = 1
    for i in range(2, n+1):
        num *= i
    return num

def is_wilson(n):
    return (fact(n-1)+1) % n**2 == 0

def rwh_primes1(n):
    """ Returns  a list of primes < n """
    sieve = [True] * (n/2)
    for i in range(3,int(n**0.5)+1,2):
        if sieve[i/2]:
            sieve[i*i/2::i] = [False] * ((n-i*i-1)/(2*i)+1)
    # return [2] + [2*i+1 for i in xrange(1,n/2) if sieve[i]]
    for i in range(1,n/2):
        if sieve[i]:
            p = 2*i + 1         # convert index to normal prime
            if is_wilson(p):    #
                yield p         #

if len(sys.argv) > 1:
    N = int(float(sys.argv[1]))
else:
    N = 10000           # default: 1e4 10,000

print [p for p in rwh_primes1(N)]

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

संपादित करें

मैंने इसके अंतिम परिणाम को याद रखने के लिए तथ्य () को इस प्रकार बदल दिया:

last_fact = 1
last_n = 1

def fact2(n):
    global last_fact, last_n
    num = last_fact
    for i in range(last_n+1, n+1):
        num *= i
    last_n = n
    last_fact = num
    return num

def is_wilson(n):
    return (fact2(n-1)+1) % n**2 == 0

इसने इसे काफी तेज कर दिया। cProfile दिखाता है कि is_wilson() अब अड़चन है। मैं इसे तेज़ बनाने का एक आसान तरीका नहीं सोच सकता।

0
Greg Ames 27 सितंबर 2019, 03:58