What is the largest prime number you ever calculated?
I had calculated this
Prime No: The number which can not divided by any other number except 1 and it self is called a prime number. Example 7 is a prime number and it can not be divided by any other number except 1 and 7.
Why Prime Number are so important?
The most popular example I know comes from Cryptography, where many systems rely on problems in number theory, where primes have an important role (since primes are in a sense the "building blocks" of numbers).
Take for example the RSA encryption system: All arithmetic is done modulo n, with n=pq and p,q large primes. Decryption in this system relies on computing Euler's phi function, φ(n), which is hard to compute (hence the system is hard to break) unless you know the prime factorization of n (which is also hard to compute unless you know it upfront). Hence you need a method to generate primes (the Miller-Rabin primarily checking algorithm is usually used here) and then you construct n by multiplying the primes you have found.
The Electronic Frontier Foundation (EFF) has announced $150,000 to the first individual or group who discovers a prime number with at least 100,000,000 decimal digits.
What is the simplest program to check whether a number is prime or not?
n = number to check
p = Boolean := true
for i=2 To n-1
if i divides n Then
p=false;
end for
if p = true
Print "No is Prime"
else
PRINT "No is not Prime"How Do i find All Prime number which is less than or equal to N
For (i=3; i<=N; i=i+2)
if(isPrime(i)=true)
PRINT iWhy i = i + 2?
Because no even number can be prime.
Now how can we improve the program to find prime number quickly?
Just take a look on first algorithm. If we replace i=2 To n-1 by i=2 To SquareRoot(n), then we can reduce the execution time of our code.
If a number n is not a prime, it can be factored into two factors a and b:
n = a*bIf both a and b were greater than the square root of n, a*b would be greater than n. So at least one of those factors must be less or equal to the square root of n, and to check if n is prime, we only need to test for factors less than or equal to the square root.
One more thing every number which is not divisible by any prime number smaller then itself is also a prime number.
EX: 17 can't be divided by 2, 3, 5, 7, 11, 13 so its a prime number, where as 51 can be divide by 3 and 17 both so its not a prime number.
Now Next thing which is interesting about Prime number is, if you multiply all prime number from 2 to n (n is any prime number) and add 1 to the result, then output will be again a prime number. Remember you have to use all the prime number including 2 and n both.
Ex: 2, 3, 5, 7 will be (2x3x5x7)+1 = 211 is also a prime number.
Proof
Let p1, p2, p3 ... pn be the first n prime number starting with 2. Let P = (p1 * p2 * p3 * . . . * pn) + 1.
So P can not be divided by any of p1, p2, p3 ... pn. So P will be a prime number.
So, take a look on following code to generate a list of prime numbers.
import java.util.Scanner;
public class FastPrime {
public static void main(String[] args) throws Exception {
CreatePrimeTable(Integer.MAX_VALUE/300);
}
public static void CreatePrimeTable(int n) throws Exception {
// Create the array.
int[] table = new int[n];
// count denotes the count of the prime numbers found so far.
int count = 0;
// add the first known prime number, auto-incrementing the count.
table[count++] = 2;
System.out.println("2");
// search for n odd numbers above 2:
for (int number = 3;number<n ; number += 2) {
// Assume it is prime unless otherwise is proven.
boolean prime = true;
for (int i = 0; table[i] * table[i] <= number; i++) {
// if it is a divisor, report not prime.
if (number % table[i] == 0) {
prime = false;
break;
}
}
// if loop terminated and a divisor has not been found,
// Add number to the list, auto-incrementing the count.
if (prime) {
table[count++] = number;
System.out.println(number);
//System.out.println("Ge");
}
}
System.out.println("-1");
// That's it.
}
}Simply save the output to a file.
Use this: java FastPrime > FastPrime.txt to save to file.
This will store all generated prime number into a file named "FastPrime.txt"
Now, I have all the prime number from 2 to 2147473(max limit) with -1 on the end of file. -1 will be used to indicate the end of the file in our next program.
Now, Friends we are only one step away from the Prime number having thousands of digits. It will contain .9 million digits. You will need 200 pages to print this single prime number. By the way, the largest prime number has approximate 17 million digit, So its very small in compare to that.
Now I need to multiply all these prime numbers. How will you multiply all of them. Of-course you can not use simple multiplication since, because there is no data type, which can hold such a number having 9 Lakhs digits.
So now we need our that method which we have learn in CLASS 1 or 2,
2 2
x 2 3
-----
6 6
4 4 x
-----
5 0 6So we have to write a generic code to do this, I know you are very intelligent but don't bother about this code. I had written that for you.
/**
* @(#)multiply.java
*
*
* @author
* @version 1.00 2015/2/15
*/
import java.util.*;
public class multiply {
public multiply() {
}
public static void main(String args[]){
int temp=0,j,x;
int m=1,i;
int per=0,tper=0;
int a[] = new int[Integer.MAX_VALUE/300];
a[0]=1;
Scanner sc = new Scanner(System.in);
int k;
k= sc.nextInt();
int nkj=0;
while(k>0)
{
nkj++;
for(j=0;j<m;j++)
{
x = a[j]*k+temp; //x contains the digit by digit product
a[j]=x%10; //Contains the digit to store in position j
temp = x/10; //Contains the carry value that will be stored on later indexes
}
while(temp>0) //while loop that will store the carry value on array.
{
a[m]=temp%10;
temp = temp/10;
m++; // increments digit counter
}
k=sc.nextInt();
per=(int)(Math.round(nkj/1600));
//System.out.println(nkj);
if(per!=tper){
System.out.print(per+"% ");
tper = per;
}
}
a[0]++;
for(i=m-1;i>=0;i--) //printing answer
System.out.print(a[i]);
System.out.println("\n\n---------------------------------\n\n");
}
}Just input our previous generated prime numbers into this. So use following command line.
java multiply <FastPrime.txt >LargestPrime.txt
Besure that all the files are in same directory. Wait for approx 20-30 min, It will took time to calculate. However you can open the LargestPrime.txt file to view the work progress. It will show you in percentage of calculation progress.
The Largest Prime will been thrown to the file "LargestPrime.txt".
Simply open the file. Be careful, you should not open this file from notepad, it will take a lot of time to open. Use wordpad to open this or any good text editor. You will find the prime number.
This is my till work. Now I am going to do following
Find (2^(p))-1 which is again a prime number (p=my largest prime number).
But i know one think, If I use the best computer of today to do this calculation 2^p, I need several year to solve it.
But I will never give up and always run to do this.
Nishant Kumar.
Any query please contact: nishant.kumar.cse16@gmail.com
Author
{"6887492": "/users/pagelets/trending_card/?sensual=True"}