Prime Crime 3

Computer Science Level 3

$\huge{\color{#69047E}{2017}}$ $\text{ What is the } 2016^{th} \text{ prime number ending with 7 ?}$

this problem is a part of set Prime Crimes via Computer Science

81817 81847 81937 81737

4 solutions

Arulx Z
Jan 23, 2016

Miller-Rabin + Brute force

import random
import sys

def prime(n, k = 7):
   """use Rabin-Miller algorithm to return True (n is probably prime)
or False (n is definitely composite)"""
   if n < 6:  # assuming n >= 0 in all cases... shortcut small cases here
      return [False, False, True, True, False, True][n]
   elif n & 1 == 0:  # should be faster than n % 2
      return False
   else:
      s, d = 0, n - 1
      while d & 1 == 0:
         s, d = s + 1, d >> 1
      # Use random.randint(2, n-2) for very large numbers
      for a in random.sample(xrange(2, min(n - 2, sys.maxint)), min(n - 4, k)):
         x = pow(a, d, n)
         if x != 1 and x + 1 != n:
            for r in xrange(1, s):
               x = pow(x, 2, n)
               if x == 1:
                  return False  # composite for sure
               elif x == n - 1:
                  a = 0  # so we know loop didn't continue to end
                  break  # could be strong liar, try another a
            if a:
               return False  # composite if we reached end of this loop
      return True  # probably prime if reached end of outer loop

count = 0
n = 3

while count < 2016:
   if n % 10 == 7:
      count += prime(n)
   n += 2

print n - 2

Moderator note:

Simple standard approach.

Well ... can you explain the logic behind that ?

Zeeshan Ali - 5 years, 4 months ago

Miller-Rabin test or the brute force part?

Arulx Z - 5 years, 4 months ago

Yes... please elaborate your logic in that solution.

Zeeshan Ali - 5 years, 4 months ago

@Zeeshan Ali – Miller-Rabin is a probabilistic primality test. I think you should read this and this to get a better idea about it.

Arulx Z - 5 years, 4 months ago

Hjalmar Orellana Soto
Feb 24, 2016

n=0
a=6
while n<2016:
    b=2
    while b<a:
        if a%b==0:
            b+=a
        else:
            b+=1
    if a==b:
        c=str(a)
        if str(a)[len(str(a))-1]=="7":
            n+=1
            print a
    a+=1

What language is that?

Zeeshan Ali - 5 years, 3 months ago

python, I did it that way because it was easier than in c++ (I'm getting started in c++)

Hjalmar Orellana Soto - 5 years, 3 months ago

Oh! I just got confused to see so much underscores ( _ ) :P

Zeeshan Ali - 5 years, 3 months ago

@Zeeshan Ali – oh, sorry, that's because I hadn't found how to write codes here as you do xD May you explain it to me, please?

Hjalmar Orellana Soto - 5 years, 3 months ago

@Hjalmar Orellana Soto – Just folow the way below:

$```python$

//code

$```$

Zeeshan Ali - 5 years, 3 months ago

You can just copy and paste your code between $" ```python " and " ``` "$

Zeeshan Ali - 5 years, 3 months ago

@Zeeshan Ali – Untill I could!! Thank you

Hjalmar Orellana Soto - 5 years, 3 months ago

@Hjalmar Orellana Soto – Any time! :)

Zeeshan Ali - 5 years, 3 months ago

Zeeshan Ali
Jan 23, 2016

Here is a C++ code to find whether a number is prime or not.

    bool is_prime(int N){
        for (int i=2; i<N/2; i++){
            if (N%i==0){
                return false;
            }
        }
        return true;
    }

I leave the further work on you all, if you don't mind :)

Shaun Leong
Jan 21, 2016

A solution using Python 2:

def isprime(n):
    i=2
    while i*i<=n:
        if n%i==0:
            return False
            break
        else:
            i+=1
    if i*i>n:
        return True
count=0
current=1
n=0
while count < 2016:
    if isprime(10*n+7):
        count+=1
        current=10*n+7
    n+=1
if count==2016:
    print "The number is ", current

That is an admirable efficient effort... :)

Zeeshan Ali - 5 years, 4 months ago

The function to find if a number is prime could be more efficient :)

Zeeshan Ali - 5 years, 4 months ago

Prime Crime 3

this problem is a part of set Prime Crimes via Computer Science

4 solutions

Moderator note:

0 pending reports