C++

Forum

 
long prime

ynooran (10)
Hello,
I have been learning c++ for two months and know the beginner stuff.
one of the assignments I have is to write a program that could produce immensely large primes. I asked our professor and he told me it had to do with displaying a few ints next to each other to create one large number.The problem is I have know idea of how to write this program. I know how to check primality but not this. How do you check if two ints next to each other are primes? Thank you in advance.
Last edited on
snowright (48)
What I understood of what you told your professor told you he suggested that the primes generated in the exercise are so large that you cannot store them in an int, so you would need to store the information of the number in more than one variable. I could be wrong though, but especially the phrase "displaying a few ints next to each other" would point into this direction.

Was there more specific information on the exercise i.e. how large exactly should the generated primes be - do we get some predefined magnitude to search a prime from? Also is it enough for the primes to be probable i.e. primes in the sense of using them for example for cryptography or do they need to be primes proved with no divisor at all.

Also is this some basic programming class you are not supposed to be studying number theory that much? There exists some easily implementable algorithms that generate all primes less than N i.e. algorithms the use of which does not require knowledge on number theory such as sieve of Eratosthenes but with which you obviously do not get that large primes. If you are really constructing very large provable primes there is a quite much reading of mathematics coming ahead before you get into programming anything.
Last edited on
ynooran (10)
Hello snowright,
Thanks for your reply.This is an example of code I have written that shows the way we are taught to find primes. What I really need to know is how can you store one number in a few variables and still do operations with it. example code from my last session.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
#include <iostream>
#include <cstdlib>
// Primes before n
using namespace std; 
int main ()
{	
	int a,b=0;
	cout<<"Enter a Number\n";
	cin>> a;
	cout<<"Primes before "<<a<<endl;
	while(a-->2)
	{
		b=a-1;
		while(b>1)
		{
			if(a%b==0)
			b=1;
			b=b-1;
		}
		if(b==1)
		cout<<a<<endl;
	}
   system("PAUSE");	
   return 0;
}
snowright (48)
I suggest that you begin to use white-space more. Here would be couple of examples from your code
1
2
3
 
int a, b = 0; //Always add space after comma and in both sides of equality sign
while(a-- > 2) //This is much clearer; you could even go further with...
while( a-- > 2 ) //... this is somehow already an opinion than objectively clearer


I think that your example kind of gives me enough information to get a hint on what level we exactly are programming here. This is just a guess (supposing we are not going to use in some way too complex algorithms for your class), but enough improvement for the code to find one large prime could be not to find all primes less than some number but simply start from a large number say N and check numbers above it one by one after we find a prime - as a result a large prime much faster than checking all numbers under N for primality.

Other general improvement would be to start checking if the number is divisible by 2 and continue to larger numbers in order: this makes your algorithm striking fast versus that old one. Notice it is much more probable that a number is divisible by smaller prime compared to large.

More improvement is ( when checking primality of N ) is to check divisibility only for numbers less than or equal to the floored square root of N, since most definitely all (prime) factors of a number cannot be larger than its square root.

Improvement would also be to check the divisibility of the number only for odd numbers ( after checking if it is divisible by two) since if the number is divisible with 2n, most definitely it was already divisible by n so no check is required for even numbers ( apart from 2 ). In practice you change to b += 2 in the loop and just add an extra check outside the loop for a%2.

What I am trying to implicate here as well is that I believe that you are not required to go over for example 4,294,967,295 or how big ever the unsigned long int can be safely assumed to be: just that this kind of calculation is relatively complex to your class at least of what I have understood from you. If you somehow disagree, come here with a comment.
Last edited on
ynooran (10)
Thank you for your reply but I wasn't asking for a way to calculate primality faster.

My main question is how to achieve a prime that is longer than an unsigned int.

Our professor told us that we could use a few integers but how?

He even gave us an example of someone who brought a 3-page prime number!
So basically a way to achieve a bigger prime not faster.
Tahnk you.

Just so you can see an example of our work, this is a program that calculates pi that I wrote:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
#include <iostream>
#include <cstdlib>
#include <cmath>
// Pi
using namespace std;
 
int main ()
{ 
 float input;
 long double x,y,a=0;
 cout<<"Please set Precision of steps (Max 1)"<<endl;
 cin>>input;// Sets step Precision
 input=pow(input,-1); 
 for ( x=0;x<=2*input;x++ )
   {
     for(y=0;y<=2*input;y++)
  	{
  		if(sqrt(x*x+y*y-2*input*(x+y)+2*input*input)<=input)
  		a++;
  	}
   }
   cout<<"Pi equals:"<<a/(input*input)<<endl;//a=pi*r^2==>a=pi*input^2==>a/input^2=pi   
   system("PAUSE"); 
   return 0;
}
Last edited on
snowright (48)
Alright, now we understand each other. The operations you need to write for the system you handle the large numbers with depend on the algorithm you would like to use for finding large primes. It would be most impressive to implement for example AKS primality test which would let you decide whether any given number is a prime or composite, this would somehow require more ( programming and time at run time to find large primes ) than for example Lucas-Lehmer test but which finds only Mersenne primes; though for my opinion there is not too large gaps between Mersenne primes, so you would find primes of any resonably wide magnitude you liked; you can check the frequency here https://en.wikipedia.org/wiki/Mersenne_prime#List_of_known_Mersenne_primes

Any algorithm you choose you will most likely need to write at least addition and multiplication for your large number objects. The basic logic that would be most easy for you to begin constructing such numbers is follows. You understand that a value stored in an int ( at its simplest, unsigned ) is the digits of its binary ( base-2 numeral system ) representation so an integer can display numbers up to 2^32 - 1 when we have 32 bits to play with. To construct a number requiring any number of bits, you simply section its first 32 bits to a first int then next 32 bits to a second int and so on: what you will end up with is an array of ints for a large number. Now for example summation for this kind of numbers should be quite straightforward. Given such numbers ( arrays of integers ) a and b the representation for their sum as a similar array c would be at simplest c[ i ] = a[ i ] + b[ i ] for each i but there is obviously a small catch. Given that the sum is larger than what an integer can represent i.e. if for example a[ 1 ] + b[ 1 ] > 2^32 - 1 we are properly getting what is more than 2^32 ( or more than 2^64 in the real value of the number ) in the c[ 1 ] but the 2^32 ( again in real value 2^64 ) must be added to c[ 2 ] where it is simply 1, so we would simply do c[ 2 ]++. I believe this is something you can quite easily come up with if you understand the basic idea. For example for such number c[3]++ would add 2^96 to the numbers real value. Multiplication is already little more complex but I will let you go by yourself for that, come here though if you feel like you need help ( well with anything basically ).

Last edited on
ynooran (10)
Sorry for the delayed reply,
as we have not learned arrayed yet I was thinking of storing a number in 6 ints,
I wrote the program but I don't
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
 
#include <iostream>
#include <cstdlib>
#include <cmath>
// Pi
using namespace std;
 
int main ()
{ 
int prime,pcheck,n,leftover;
int a=999,b=999,c=999,d=999,e=999,f=999;
unsigned a2=a,b2=b,c2=c,d2=d,e2=e,f2=f;
cout<<a<<b<<c<<d<<e<<f<<endl;
for(prime=0;prime==0;f=f-2)
{
	if(f=-1)
	{
	f=999;
	e=e-1;
	}
	if(e=-1)
	{
	e=999;
	d=d-1;
	}
	if(d=-1)
	{
	d=999;
	c=c-1;
	}
	if(c=-1)
	{
	c=999;
	b=b-1;
	}
	if(b=-1)
	{
	b=999;
	a=a-1;
	}
	a2=a;
	b2=b;
	c2=c;
	d2=d;
	e2=e;
	f2=f;
	for(pcheck=3;pcheck<1000000000;pcheck=pcheck+2)
	{
		
		b2=b2+(a2%pcheck)*1000;
		c2=c2+(b2%pcheck)*1000;
		d2=d2+(c2%pcheck)*1000;
		e2=e2+(d2%pcheck)*1000;
		f2=f2+(e2%pcheck)*1000;
		if(f2%pcheck==0)
		pcheck=1000000000;				
	}
	if (pcheck!=1000000002)
	{	
		cout<<"Here:"<<a<<endl;
		cout<<"Here:"<<b<<endl;
		cout<<"Here:"<<c<<endl;
		cout<<"Here:"<<d<<endl;
		cout<<"Here:"<<e<<endl;
		cout<<"Here:"<<f<<endl;
		cout<<"Here2:"<<a2<<endl;
		cout<<"Here:"<<b2<<endl;
		cout<<"Here:"<<c2<<endl;
		cout<<"Here:"<<d2<<endl;
		cout<<"Here:"<<e2<<endl;
		cout<<"Here:"<<f2<<endl;
		prime=1;
	}
}
return 0;
}
know whats wrong.
snowright (48)
I must say my manner of an approach ( the one I explained ) is so much better. You know, sometimes universities or wherever you study at teach things in the wrong order, for example this task of finding large prime is ridiculous if you do not use arrays, so say what: read http://www.cplusplus.com/doc/tutorial/arrays/ it will not take long from you I promise. Were you slowly learning anyway less than 30 minutes and you will understand everything. Computing primes will after that make a whole lot of more sense.
long double main (999)
If you're okay with primes up to 18446744073709551557, use unsigned long long.

If you want primes bigger than that, either look into an arbitrary-precision number library (like http://gmplib.org/ ) or implement your own biginteger class. Without arrays of some kind, you really can't get very far at all.

In terms of primality testing, if this is what you have to check if a number is prime:
1
2
3
4
5
6
7
8
9
10
11
12
 
bool isPrime(unsigned int n)
{
    if (n < 2) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;

    for (unsigned i = 3; i <= sqrt(n); i += 2)
        if (n % i == 0)
            return false;

    return true;
}

then I'm afraid that you won't be able to get much farther than about 260-ish (depending on the speed of your computer).

If the Miller-Rabin probable prime test (http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test ) is beyond what you guys are expected to know for the class, then I have no clue how your professor could possibly expect you guys to be able to generate huge primes.

(Easy way out: Use GMP, make some big numbers, and use mpz_nextprime to get the next biggest prime.)

EDIT: In terms of finding 3-page-long primes, I don't know what font size (or page size) that guy was using, but the only primes that we know of that could possibly be big enough to fill that kind of space are Mersenne primes, so you'd probably just have to look up some of the bigger ones and implement some kind of way to print them onto the screen (or to a file).

And just for kicks, here's a 2048-bit prime number for you:
30764335913224293741793089483751460355175991453129092078243105216768983877701064
20152058813510372450551680165583388871577022945546276716267073172921327646162793
41664497883199600833501370142076564681452764613152016012206236573517386019095119
98767856127706785772715433996063691574284036280147349001102050746978709482330269
11500093820666704387895922245667063882347947007089909496758327065159950605733832
84482832596079515169543633486785256763428598933862730293253731564125649671376639
63731303860917438373004747773817080905869559476141139949839173942264517057599758
575128777806956660641436317136340480429016551699604867739
Last edited on
ynooran (10)
After doing some research I have settled to finding a way to generate and display a long mersenne prime. But I just don't know how?

How can I have 2^p when it is longer than a long long unsigned int?


Thanks
snowright (48)
long double main, your proposition that the only primes that could possibly fill three pages in their representation would be Mersenne primes is ridiculous. The largest known Proth prime 19249 ยท 2^13018586 + 1 which is the largest known nonmersenne prime as well has 3918990 digits ( base-10 ) and I am quite sure using a font so small that you would be able to fit nearly four million characters to less than three pages is in no way reasonable. More clearly, our knowledge or knowledge of mathematicians at least in generating large primes, were their magnitude three pages or hundred pages, is quite more advanced than what you thought. I for example already mentioned general primality-proving algorithm, more specifically AKS primality test.

ynooran, I tried to explain that already to you, even explained that you should learn to use arrays before implementation, could you again consider reading little about arrays before continuing?
Last edited on
long double main (999)
@snowright
Sorry, I must have been (sorely) overestimating the number of characters that can fit in a single page. (Okay, maybe if you take a HUGE page and SUPER tiny digits, then....)
I'm certainly aware that there are huge primes out there that aren't Mersenne primes (in fact, most of them aren't), but again, I probably just overestimated how many characters could fit in one page, so I erroneously assumed that you'd have to take one of the top 10 largest known primes (all of which are currently Mersenne primes) in order to do it. (Now that I think about it, that does sound kind of ridiculous)

I pointed out the Miller-Rabin test as perhaps one of the more simpler methods of testing if a number is (probably) prime. I'm aware that there are others out there (some of which are deterministic, like AKS (which you mentioned) or ECPP (which I think is one of the faster ones)), but I don't know how hard those are to implement (honestly, I haven't really tried...), so I just mentioned the Miller-Rabin test as a "if this algorithm is too hard for you, then maybe you're setting your sights a bit too high" kind of thing.

Anyways, back on topic now...
ynooran (10)
Thanks everyone I managed to write the code succesfully! :)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
 
#include <iostream>
#include <cstdlib>
#include <cmath>
// Mersene Prime Calculator
using namespace std;
 
int main ()
{
	int input,counter;
	cout<<"Enter a Mersenne Number to see it's prime\n"<<endl; 
	cin>>input;
	unsigned long long int a=0,b=0,c=0,d=0,e=0,f=0,g=0,h=0,i=0,j=0,k=0,l=1;
	for(counter=0;counter<input;counter++)//What this does: 2^input
{
	a*=2;
	b*=2;
	c*=2;
	d*=2;
	e*=2;
	f*=2;
	g*=2;
	h*=2;
	i*=2;
	j*=2;
	k*=2;
	l*=2;
	if(l>=pow(10,18))
	{k=k+(floor (l/pow(10,18)));l=l-((floor (l/pow(10,18)))*pow(10,18));}
	if(k>=pow(10,18))
	{j=j+(floor (k/pow(10,18)));k=k-((floor (k/pow(10,18)))*pow(10,18));}
	if(j>=pow(10,18))
	{i=i+(floor (j/pow(10,18)));j=j-((floor (j/pow(10,18)))*pow(10,18));}
	if(i>=pow(10,18))
	{h=h+(floor (i/pow(10,18)));i=i-((floor (i/pow(10,18)))*pow(10,18));}
	if(h>=pow(10,18))
	{g=g+(floor (h/pow(10,18)));h=h-((floor (h/pow(10,18)))*pow(10,18));}
	if(g>=pow(10,18))
	{f=f+(floor (g/pow(10,18)));g=g-((floor (g/pow(10,18)))*pow(10,18));}	
	if(f>=pow(10,18))
	{e=e+(floor (f/pow(10,18)));f=f-((floor (f/pow(10,18)))*pow(10,18));}
	if(e>=pow(10,18))
	{d=d+(floor (e/pow(10,18)));e=e-((floor (e/pow(10,18)))*pow(10,18));}
	if(d>=pow(10,18))
	{c=c+(floor (d/pow(10,18)));d=d-((floor (d/pow(10,18)))*pow(10,18));}
	if(c>=pow(10,18))
	{b=b+(floor (c/pow(10,18)));c=c-((floor (c/pow(10,18)))*pow(10,18));}
	if(b>=pow(10,18))
	{a=a+(floor (b/pow(10,18)));b=b-((floor (b/pow(10,18)))*pow(10,18));}		
}
	cout<<"Prime:"<<endl<<a<<b<<c<<d<<e<<f<<g<<h<<i<<j<<k<<l-1<<endl;
 return 0;
}
/*
Enter a Mersenne Number to see it's prime

607
Prime:
05311379928167668776963527775300432691230828002112280985667021944881886003261444
97287621509123871739707887452168914081851469987842907556477576151047502783979430
87104835393219031728127

--------------------------------
Process exited with return value 0
Press any key to continue . . .
*/

But one question, if my professor asked me how I calculated 607 as a merssene power what shoud I say in return?

Is there any algorithm to calculate the 607 power?

The prime I calculated was 2^607-1
Last edited on
ynooran (10)
With array:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
 
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <fstream>
// Mersene Prime Calculator
using namespace std;
 
int main ()
{
	ofstream file;
    file.open("Prime.txt");
	int i,counter;
	unsigned long long int a[116609];
	for(i=0;i<116609;i++)
	{
		a[i]=0;
	}
	a[116608]++;
	for(counter=0;counter<6972593;counter++)
	{
		cout<<counter<<endl;
		for(i=0;i<116609;i++)
		{
			a[i]*=2;
		}
		for(i=116608;i>0;i--)
		{
			if(a[i]>=pow(10,18))
			{a[i-1]=a[i-1]+(floor (a[i]/pow(10,18)));a[i]=a[i]-((floor (a[i]/pow(10,18)))*pow(10,18));}	
		}
	}
	for(i=0;i<116608;i++)
	{
		file<<a[i];
	}
	file<<--a[116608]<<endl;
	file.close();
	return 0;
}


Any ideas anyone to improve speed?
Topic archived. No new replies allowed.