Newer
Older
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
/* next-prime.c
*
* Command line tool for prime search.
*
*/
/* nettle, low-level cryptographics library
*
* Copyright (C) 2007 Niels Mller
*
* The nettle library is free software; you can redistribute it and/or modify
* it under the terms of the GNU Lesser General Public License as published by
* the Free Software Foundation; either version 2.1 of the License, or (at your
* option) any later version.
*
* The nettle library is distributed in the hope that it will be useful, but
* WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
* or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
* License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with the nettle library; see the file COPYING.LIB. If not, write to
* the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
* MA 02111-1307, USA.
*/
#if HAVE_CONFIG_H
# include "config.h"
#endif
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "bignum.h"
#include "getopt.h"
static void
usage(void)
{
fprintf(stderr, "Usage: next-prime [OPTIONS] number\n\n"
"Options:\n"
" --help Display this message.\n"
" -v, --verbose Display timing information.\n"
" --factorial Use factorial of input number.\n"
" -s --sieve-limit Number of primes to use for sieving.\n");
}
int
main(int argc, char **argv)
{
mpz_t n;
mpz_t p;
int c;
int verbose = 0;
int factorial = 0;
int prime_limit = 200;
enum { OPT_FACTORIAL = -100 };
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
static const struct option options[] =
{
/* Name, args, flag, val */
{ "help", no_argument, NULL, '?' },
{ "verbose", no_argument, NULL, 'v' },
{ "factorial", no_argument, NULL, 'f' },
{ "sieve-limit", required_argument, NULL, 's' },
{ NULL, 0, NULL, 0}
};
while ( (c = getopt_long(argc, argv, "v?s:", options, NULL)) != -1)
switch (c)
{
case 'v':
verbose = 1;
break;
case '?':
usage();
return EXIT_FAILURE;
case 'f':
factorial = 1;
break;
case 's':
prime_limit = atoi(optarg);
if (prime_limit < 0)
{
usage();
return EXIT_FAILURE;
}
break;
default:
abort();
}
argc -= optind;
argv += optind;
if (argc != 1)
{
usage();
return EXIT_FAILURE;
}
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
mpz_init(n);
if (factorial)
{
long arg;
char *end;
arg = strtol(argv[0], &end, 0);
if (*end || arg < 0)
{
fprintf(stderr, "Invalid number.\n");
return EXIT_FAILURE;
}
mpz_fac_ui(n, arg);
}
else if (mpz_set_str(n, argv[0], 0))
{
fprintf(stderr, "Invalid number.\n");
return EXIT_FAILURE;
}
if (mpz_cmp_ui(n, 2) <= 0)
{
printf("2\n");
return EXIT_SUCCESS;
}
mpz_init(p);
start = clock();
nettle_next_prime(p, n, 25, prime_limit, NULL, NULL);
end = clock();
mpz_out_str(stdout, 10, p);
printf("\n");
if (verbose)
{
mpz_t d;
mpz_init(d);
mpz_sub(d, p, n);
/* Avoid using gmp_fprintf, to stay compatible with gmp-3.1. */
fprintf(stderr, "bit size: %lu, diff: ", (unsigned long) mpz_sizeinbase(p, 2));
mpz_out_str(stderr, 10, d);
fprintf(stderr, ", total time: %.3g s\n",
(double)(end - start) / CLOCKS_PER_SEC);