Do They Satisfy? (Part 1)

Computer Science Level 3

For the next few problems of this series, you will be given a property $P$ and a bunch of (usually $8$ ) numbers or expressions. Your answer will be an $n$ -digit number, where $n < 10$ is the number of numbers or expressions given. For the $k$ -th number or expression, if it satisfies property $P$ , then on the $k$ -th digit of your answer, enter $k$ . If not, enter $0$ as the $k$ -th digit. For example, if $P$ : even, and there are $3$ numbers, $4, 7, 3182$ . Then, enter your answer as $103$ .

$P$ : primes

$2$
$65537$
$2999999$
$4999999$
$98320414332827$
$2^{35} - 1$
$34567875111$
$12345678987654321$

You can try Part 2 and Part 3 .

The answer is 12340000.

10 solutions

Discussions for this problem are now closed

Thaddeus Abiy
Feb 10, 2014

There are many primality tests around. A simple and common algorithm is just checking weather any number below $\sqrt{N}$ divides the number. Unfortunately the large input of this problem renders it unusable.The Miller-Rabin test is an excellent primality test(atleast practically) and is based on the contrapositive of Fermat's little theorem ..

The test implemented in python below determines numbers $1,2,3,4$ to be prime and the rest composite,hence the answer $12340000$ .

def isprime(n):
    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1
    for a in (2,3,5,7,11,13,17,19,23,29):
        if a >= n:
            return True
        def t(x, n, s):
            if x == 1 or x == n - 1:
                return True
            for r in range(1, s):
                x = pow(x, 2, n)
                if x == 1:
                    return False
                if x == n - 1:
                    return True
            return False
        if not t(pow(a, d, n), n, s):
            return False
    return True
print isprime(2),isprime(65537),isprime(2999999),isprime(4999999),isprime(98320414332827),
print isprime((2**35)-1),isprime(34567875111),isprime(12345678987654321)

EDIT:Note that the Miller Rabin test is randomized and is usually referred to as a probabilistic algorithm.More powerful deterministic algorithms such as AKS exist(Discovered in 2002, by Agrawal, Kayal, and Saxena) but Miller-Rabin is widely used because of its speed..

I assumed this is a cs problem..

Thaddeus Abiy - 7 years, 4 months ago

Partly cs, partly maths.

Zi Song Yeoh - 7 years, 4 months ago

Nice code. It would be good to tell expressly what the limits of the test are.

Also I copied and tested it for my own edification. I was able to detect 2 typos. A bad indent at line 18: return True. And the number is 65537.

Steven Perkins - 7 years, 3 months ago

Thanks .. corrected the typos..

Thaddeus Abiy - 7 years, 3 months ago

public class prime {

public static void main(String[] args) {
    Long number,i,j;
    Boolean flag=false;
    number=12345678987654321L;
    if(number%2!=0){
        for(i=3L;i<=Math.sqrt(number);i=i+2){

            if(number%i==0){
                flag=true;
                System.out.println("not a prime.. factor is "+i);
                break;
            }

            }
        if(!flag){
            System.out.println("prime");
        }

    }



    else
    {
        System.out.println("divisible by 2 .. not a prime");
    }
}

}

Vinay Kr - 7 years, 3 months ago

can u explain it

navdeep kaur - 7 years, 3 months ago

Nilesh Sah
Feb 17, 2014

include <iostream>

#include <conio.h>
#include <math.h>
using namespace std;

int main() {
long long int x = 12345678987654321, i, j;
j = sqrt(x);

for( i = 2; i < j; i++ )
     if( x%i == 0 ) {
         cout << "No";
         getch();
         exit(0);
     }

cout << "Yes";
getch();

}

Use the above code and keep modifying the value for x; Final Answer: 12340000

Amit Patel
Apr 17, 2014

A simple Haskell code to test the prime number... :

isPrime :: Integer->Bool

isPrime x = null [y | y<-[2..floor (sqrt (fromIntegral x))], x mod y == 0]

Irvin Denzel Torcuato
Mar 10, 2014

I used this code to solve the problem. Implementation of isprime is not correct, the code is just intended to solve the given problem.

def isprime(n):
    i = 2
    while i <= n//2:
        if n % i == 0:
            return False
        i += 1
    return True
i = 1
print(i if isprime(2) else 0, end="")
i += 1
print(i if isprime(65537) else 0, end="")
i += 1
print(i if isprime(2999999) else 0, end="")
i += 1
print(i if isprime(4999999) else 0, end="")
i += 1
print(i if isprime(98320414332827) else 0, end="")
i += 1
print(i if isprime(2**35 - 1) else 0, end="")
i += 1
print(i if isprime(34567875111) else 0, end="")
i += 1
print(i if isprime(12345678987654321) else 0, end="")

Rajarshi Biswas
Mar 4, 2014

include<stdio.h>

include<math.h>

int isPrime(long long int n) { long long int limit=sqrt(n); long long int i; if(n%2) { for(i=3;i<=limit;i+=2) if(n%i==0) return 0;/ not prime / } else { if(n==2) return 1; return 0; } return 1; } int main() { long long int a[]={2,65537,2999999,4999999,98320414332827,34359738367,34567875111,12345678987654321}; int i; for(i=0;i<8;i++) printf("%d",(isPrime(a[i])?(i+1):0)); return 0; }

Ramkrushna Pradhan
Mar 1, 2014

x = input("Enter A No : ")

y = x**0.5

y = y//1

z = 1

while y != 0:

if x%y == 0:

     z = z + 1

y = y - 1

if z > 1:

print("not prime")

nice

navdeep kaur - 7 years, 3 months ago

Daniel Lim
Feb 27, 2014

I created a program to test if every number is a prime

Here is my program

It is C++

Daniel Lim - 7 years, 3 months ago

Nimisha Soni
Feb 25, 2014

The answer is 1234000

since 2 is prime, 65537 is prime, 2999999 is prime and 4999999 is prime. Rest all are not prime.

   #include <stdio.h>

   main()
  {
   long long x,i;
   int count=0;
  printf("Enter the number you want to check");
  scanf("%l64d",&x);
  i=1;
  for(i=1;i<=x;i++)
  { 
     if((((int)x)%((int)i))==0)
     {
         count++;
     }
  }
  if(count>2)
  {
      printf("Number is not prime");
  }
  else
  {
      printf("Number is prime");
  }
  return 0;
}

Sai Ram
Feb 24, 2014

include<iostream..h>

include<conio.h>

void main() { long long int s,i; clrscr(); cout<<"enter the number\n"; cin>>s; int flag=0,k=0; for(i=2;i<s;i++) { if(s%i==0) { k=1; } if(s%i!=0) { flag=1; } if(flag==1&&k==0) { cout<<"\n entered number"<<s<<"is prime number"; } else { cout<<"\n entered number"<<s<<"is not prime number"; } getch(); }

Siddharth Kannan
Feb 23, 2014

Python solution for above problem:

import math

def prime(n):

    k = math.sqrt(n)

    i = 2

    while i < k:

        if n % i == 0:

            return False

        i += 1

    return True

f = [2, 65537, 2999999, 4999999, 98320414332827, 2**35-1, 34567875111, 12345678987654321]


str1 = ""

for k, j in enumerate(f):

    if prime(j):

        str1 += str(k+1)

    else:

        str1 += "0"

print str1

A much efficient, much faster code.(java)

private static boolean isPrime(Long n) {
if( n == 2) 
 return true;
if (n % 2 == 0)
return false;
// if not, then just check the odds
for (int i = 3; i * i <= n; i += 2) {
            if (n % i == 0)
                return false;
        }
        return true;
    }

Ab Su - 7 years, 2 months ago