fork download
copy 
  1. #include <iostream>		// entrada salida
  2. #include <math.h>  		// funciones matematicas
  3. #include <stdio.h>      // printf, scanf, puts, NULL
  4. #include <stdlib.h>     // srand, rand
  5. #include <time.h>       // time
  6.  
  7. using namespace std;
  8.  
  9. //-----------------------------------------------------------------
  10.  
  11. double Power2( double k )
  12. {
  13. 	return pow ( k, 2.0 );
  14. }
  15.  
  16. //-----------------------------------------------------------------
  17.  
  18. unsigned long Random( unsigned long a, unsigned long b )
  19. {
  20. 	unsigned long r;
  21.  
  22. 	// Inicializa random seed
  23. 	srand ( time( NULL ) );
  24.  
  25. 	// Genera un numero entre a y b
  26. 	r = ( rand() % ( b - a + 1 ) ) + a; 
  27.  
  28. 	return  r;
  29. }
  30.  
  31. int primosBajos[] = { 2,3,0 };
  32.  
  33. //-----------------------------------------------------------------
  34.  
  35. bool TrialDivision( unsigned long a, unsigned long b  )
  36. {
  37. 	bool noDivisible = true;
  38. 	int i = 0;
  39.  
  40. 	do 
  41. 	{
  42. 		if ( a % primosBajos[i] == 0 ) 
  43. 		{
  44. 			noDivisible = false;
  45. 		}
  46.  
  47. 		i++;
  48. 	} while ( ( primosBajos[i] != 0 ) && ( primosBajos[i] <= b ) && ( noDivisible == true ) );
  49.  
  50. 	return a;
  51. }
  52.  
  53. //-----------------------------------------------------------------
  54.  
  55.  
  56. bool PrimeTest( unsigned long a ) 
  57. {
  58.     if ( a <= 3 ) 
  59. 	{
  60.         return a > 1;
  61.     } 
  62. 	else if ( a % 2 == 0 || a % 3 == 0 ) 
  63. 	{
  64.         return false;
  65.     } 
  66. 	else 
  67. 	{
  68.         for ( unsigned short i = 5; i * i <= a; i += 6 ) 
  69. 		{
  70.             if ( a % i == 0 || a % (i + 2) == 0 ) 
  71. 			{
  72.                 return false;
  73.             }
  74.         }
  75.         return true;
  76.     }
  77. }
  78.  
  79. //-----------------------------------------------------------------
  80.  
  81. float GenerateRelativeSize( )
  82. {
  83. 	float a;
  84. 	return a;
  85. }
  86.  
  87. //-----------------------------------------------------------------
  88.  
  89. bool CheckLemma1( unsigned long n, unsigned long a, unsigned long q )
  90. {
  91. 	return a;
  92. }
  93.  
  94. //-----------------------------------------------------------------
  95.  
  96. void FastPrime( int k, unsigned long p )
  97. {
  98.  
  99. 	const float c_opt = 0.1;
  100. 	const int P0 = 10000000;
  101. 	const int margin = 20;
  102.  
  103. 	unsigned long a, n, q, I, R;
  104. 	int  g;
  105. 	bool success;
  106. 	float relative_size;
  107.  
  108. 	if ( k <= P0 )
  109. 	{
  110. 		do 
  111. 		{
  112. 			n = Random ( Power2( k - 1 ), Power2( k ) - 1 );
  113. 		} while ( PrimeTest(n) );
  114. 		p = n;
  115. 	}
  116. 	else
  117. 	{
  118. 		g = c_opt * k * k;
  119. 		do
  120. 		{
  121. 			relative_size = GenerateRelativeSize();
  122. 		} while ( k * relative_size < k - margin );
  123.  
  124. 		FastPrime( trunc ( relative_size * k ), q );
  125.  
  126. 		success = false; I = (unsigned long)Power2 ( k -1 ) / q;
  127.  
  128. 		do
  129. 		{
  130. 			R = Random ( I, 2 * I );
  131. 			n = 2 * Random ( I, 2 * I ) * q + 1;
  132. 			a = Random ( 2, n - 1 );
  133. 			if ( TrialDivision ( n,g ) )
  134. 			{
  135. 				success = CheckLemma1( n, a, q );
  136. 			}
  137. 		} while ( !success );
  138. 		p = n;
  139. 	}
  140. }
  141.  
  142. //-----------------------------------------------------------------
  143.  
  144. int main() {
  145. 	// your code goes here
  146. 	return 0;
  147. }
  148.  
  149.  
Success #stdin #stdout 0s 3336KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/9bGJgq
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!