FAQ Database Discussion Community

## Code to find any prime number not working as expected

python-2.7,primes
I wrote this python code to find any prime number, the 1st, 2nd, 1000th, etc. I ran the code and it returned this, no matter what integer I entered: 2 is the 1 prime 3 is the 2 prime 5 is the 3 prime 7 is the 4 prime Here...

## Detect if input is a prime number in PHP - concerned with best practice code syntax [duplicate]

php,primes
This question already has an answer here: A formula to find prime numbers in a loop 10 answers I'm teaching my wife to code, so we made a simple prime-number detector. We came up with this, but I'm wondering if there's a better / neater way. I particularly don't...

## computing prime factors using same code produces different results?

f#,primes,biginteger
I am basically trying to compute the factors of a BigInteger that are a prime, I have two simple factorization functions, they both look like they should produce the same result in the way I used them here down below but this is not the case here, can someone explain...

## primes, logarithms, summations and loops

python,loops,sum,primes,logarithm
I'm trying to make a program to compute all primes smaller than a given number, and the natural logarithm of the product of all those primes. So because we're working with logarithms I could also just add the natural logarithm of each prime smaller than the given number. So I...

## memoization and prime number generation using sieve of eratosthenes using maps

c++,primes,sieve-of-eratosthenes
#include<iostream> #include<map> #include<algorithm> #include<math.h> using namespace std ; map< long long int , long long int > prim ; map< long long int , long long int >::iterator it ; int c, counter, check ; long long int b ; int prime( long long int t) { if( t==1 )...

## JavaScript Find Prime Numbers

javascript,primes
I have to set all the indexes in an array equal to 1. Then I have to find which indexes are not prime and set them equal to 0. Then print out all the indexes of the array that are equal to 1(prime). I can't get the part that sets...

## Prime numbers as public key - clarification?

security,certificate,primes,prime-factoring
I've read here that : If you’ve watched a security certificate being generated on your computer ..., here is exactly what happens – it produces two large numbers , checks that they are both prime and multiplies them together. This gives you your “public key”, which you can share freely...

c++,algorithm,primes
Here is the problem I am trying to solve: Define a class named PrimeNumber that stores a prime number. The default constructor should set the prime number to 1. Add another constructor that allows the caller to set the prime number. Also, add a function to get the prime number....

## Copying from input to the output text file

c++,file-io,primes
Hi guys here is my functional code but it does not works properly it should do read numbers from input.txt and count the sum of even,odd numbers in each line then conjunction of prime numbers( which does correctly) and also copy all numbers which are prime to the output.txt here...

## Beginner prime factorization

python,primes,factors
I wrote a beginner program that aims to find and print the prime factors of any number: def is_prime(n): if n == 3: return True elif n == 4: return False else: n = int(n**0.5)+1 for i in range(2,n): if n % i == 0: return False return True def...

## Prime finder code

c,primes
It's saying the program has stopped working as soon as I put an input and press enter.Can't seem to find the reason though. #include<stdio.h> int main() { int n; scanf("%d", &n); int m,f,count,i; m = 2; count = 0; while(m>=2){ f = 0; for(i=0; i*i<m; i++){ if(m%i==0){ f = 1;...

## Why doesn't my program find the 10001st prime? [Project euler-problem7]

java,primes
My problem is my program doesn't find the 10001st prime. So it never stops and I still don't know the 10001st prime. I will be happy to solve the problem with my implementation. Thank you :) public class problem7 { public static boolean sonuc=true; public static void asalmi(int j) {...

## issues trying to make rows in c program

c,loops,rows,primes
#include <stdio.h> int prime(int limit,int col); int main(){ int limit,col,count,i; printf("Table of Primes\n"); printf("===============\n"); printf("Upper limit: "); scanf("%d",&limit); getchar(); printf("# of columns: "); scanf("%d",&col); count=prime( limit,col); return 0; } int prime(int limit,int col){ int i,j,w; for(w=0;w<col;w++){ for(i=2;i<=limit;i++){ for(j=2;j<=i;j++){ if(i%j==0){ break; } } if(i==j){ printf("%d ",i); } } printf("\n"); } }...

## How to allow more entry and return factors for Prime Checker [Java]?

java,math,numbers,logic,primes
I set out to write a Prime Number Checker: import java.util.Scanner; public class PrimeChecker { int userEntry; int even_check; int odd_check; final void run(String[] args) { Scanner jaiho = new Scanner(System.in); System.out.printf("Please enter a prime number: %n"); userEntry = jaiho.nextInt(); even_check = userEntry % 2; // This is to get...

## F# finding only prime numbers

f#,primes
I'm recently new to F# so please bear with me. The problem i have is I'm trying to find only prime numbers. I've write this code: let isPrime n = let rec check i = i > n/2 || (n % i <> 0 && check (i + 1)) check...

## Function not displaying correct results

javascript,html,arrays,primes,factors
I have a factor finder that I have programmed that is supposed to start by checking if the value entered in the input box is 1 or 0 so it would display "The factor of 1 is 1." or "The factor of 0 is 0.", but when I enter the...

## Why not work with numbers greater than 10 digits?

c,rsa,primes
Hello community I have the following problem The following code does not converge to any solution for numbers exceeding 10 digits, and do not know where the problem can be as knowing that the number is prime would be met Fermat's little theorem in one call function. #include <stdio.h> #include...

## Haskell Sieve of Eratosthenes with list of composites

I have to implement the classic problem of the Sieve of Eratosthenes in Haskell for a project. Rather than computing each prime I only have to compare numbers between lists. For instance I pass a list of potential primes (parameter 1) and a list of composites (list 2). sieve [2..10]...

## Value Keeps Returning Early

ruby,return-value,primes
I'm writing a method that keeps returning a value early. I know how to write in a different way, but I would like to understand why writing it this way keeps returning the wrong value. I'm trying to get the "nth" prime number, and the below method seemingly works, and...

## Chain of Sieves to generate prime numbers C++

c++,primes,sieve
I'm trying to feed each prime number found into a chain of "sieve" objects. The below code achieves what I eventually want to do, but each sieve (Prime number)class is manually implemented (to check subsequent numbers are divisible by the stored prime then they should be discarded, otherwise they should...

## R: Split data frame when number of columns is a prime

r,split,data.frame,primes
I have a data.frame that has 131 columns. I need to part this into groups of about 10 to 15 variables (i.e., splitting by column, not by row!). Obviously, as 131 is a prime number, not all the new dataframes can be of equal length... I searched for an answer...

## Enumerate factors of a number directly in ascending order without sorting?

algorithm,primes,enumeration,factors
Is there an efficient algorithm to enumerate the factors of a number n, in ascending order, without sorting? By “efficient” I mean: The algorithm avoids a brute-force search for divisors by starting with the prime-power factorization of n. The runtime complexity of the algorithm is O(d log₂ d) or better,...

## Convert double to Int64 in swift

ios,swift,ios7,casting,primes
I'm a beginner to swift. I'm just trying out to write a program to print nth prime, but having some trouble converting sqrt function to int. Below is the code which works fine with c/c++. func nthPrime(n: Int64) { var i:Int64=4,j:Int64=0, prime:Int64=0 var count:Int64=0 while count != n { for...

## c# - Print the prime numbers from 0 to 10,000

c#,for-loop,numbers,primes,do-while
Im currently trying to create a program that prints the prime numbers from 0 to 10,000 using only for,do while and ifs. I created this program but it doesn't runs static void Main(string[] args) { for (int x = 2; x < 10000; x++) { for (int y = 1;...

## Adding wheel factorization to an indefinite sieve

python,primes,infinite,sieve-of-eratosthenes,wheel-factorization
I’m modifying an indefinite sieve of Eratosthenes from here so it uses wheel factorization to skip more composites than its current form of just checking all odds. I’ve worked out how to generate the steps to take to reach all the gaps along the wheel. From there I figured I...

## How to make the Sieve of Eratosthenes faster?

python-3.x,primes,sieve-of-eratosthenes,number-theory
I am trying to solve the 10 problem in the Project Euler. It consists on finding the sum of all the primes below two million. I wrote the following code based on the Sieve of Eratosthenes. import time t0 = time.time() n=200000 liste=list(range(2,n)) k=2 s=2 while k <=n: liste=list(set(liste)-set(range(k,n,k))) if...

## Next prime number algorithm

algorithm,primes
i want to know if there is a easy way to find the prime number next to X. For example, if X=2, the next prime will be 3. The algorithm that i have would be ok, if i wanted to know little numbers but i want to calculate like X=3...

## Problems with prime number generator, using ArrayList

java,arrays,arraylist,primes
I have been having a heck of a time trying to make a prime number generator work. It's supposed to list the first 100 primes, so sieving means either cheating and looking up an artificial limit to the composites, or creating a bunch of needless arrays of composite numbers. Just...

## prime number nth length

javascript,for-loop,primes
I need a way to find the 10001th prime number. My code prints out all the prime numbers but I'm not sure how to get the 10001th prime number. function prime(nth) { var arr = [2]; var isPrime = true; for(var i = 3; i <= 100; i++) { isPrime...

## How can I add the outcome of a function to a list in python?

python,list,primes
def b(): a = int(input("Look up to: ")) // set the range to scan for primes for num in range(0, a): if prime(num) == True: print(num) print("adding to list") return num list = [num] list.append(num) else: print(num, "is not a prime") So how can I append the outcome to "list"...

## Generating tuples of primes with a list comprehension, each tuple having higher sum

I searched, but I didn't find something that helped, so I post a new question. I am learning Haskell, and this is an exercise I don't understand. I want to create an infinite list of tuples of prime numbers, each tuple's sum being a higher even number, beginning with 2....

## Implementing a prime number counter

c++,algorithm,math,primes
For some reason, my last prime(int prime) isn't showing up at the end. Any clue ? fyi: primeEval stands for a flag, if the loop ends && primeEval==2, the number is actually a prime number. qty stands for quantity of primes counted. int main(){ long primeEval=0,prime=0,qtyprime=0; time_t timerr=(time(NULL)+10); for (int...

## Finding the n largest primes under m

python,algorithm,primes,prime-factoring
The algorithm below is the Sieve of Eratosthenes which I have implemented in Python. This algorithm finds the first primes up to a given value, namely n. The way this algorithm works is by printing all primes starting from 2 up to n. What I want to do is the...

## Why is my Sieve of Eratosthenes so slow?

python,performance,algorithm,time-complexity,primes
Im solving some problems on Project Euler and had to generate 2 million primes to solve a problem. My implementation of the Sieve of Eratosthenes turned out to be EXTREMELY slow but I don't quite know why. Could someone please explain the major problems with this implementation. I thought it...

## Prime numbers on r

r,primes
Hey i want to write a function in R which accepts a list of integers and returns only the values which are prime. So far i have this: > primefindlist<-function(n){ + return(n[n==2 | all(n %% seq(2,ceiling(sqrt(n)),by=1) !=0)]) + } But i keep getting an error message when i run the...

## finding the lowest collatz sequence that gives more that 65 primes

python,sequence,primes,collatz,memorization
I have a task where I need to find the lowest Collatz sequence that contains more than 65 prime numbers in Python. For example, the Collatz sequence for 19 is: 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2,...

## Display Prime numbers with MVC Java

java,model-view-controller,primes
I have a Prime class which extends JFrame and it has a simple JSpinner for displaying prime numbers. I want to create a Model for displaying prime numbers infinitely (until long ends). Here is the model class I have written: public class PrimeSpinnerModel extends AbstractSpinnerModel{ long current; public PrimeSpinnerModel() {...

## Cannot implicitly convert type 'ulong' to 'bool'

c#,primes
I get this error: Cannot implicitly convert type 'ulong' to 'bool' in here (u*u) for (ulong u = 2; u * u; u++) chunk of code below. static bool IsPrime(ulong Num) { if (Num < 2) return false; else if (Num < 4) return true; else if (Num % 2...

## Converting into a function

c,function,while-loop,primes
This program works fine for me but I've been trying to find a way to include a function that will find me the prime numbers I'm looking for. I just don't understand how to place a function into my program. The program finds twin primes inside a given interval in...

## Is Rabin-Miller primality test algorithm using modular squaring correct?

python,algorithm,primes,algebra
I have recently come across this piece of code for Rabin-Miller algorithm, as decribed here: from random import randint def _bits_of_n(n): """ Return the list of the bits in the binary representation of n, from LSB to MSB """ bits = [] while n: bits.append(n % 2) n /= 2...

## Adding elements to an array - Pascal

arrays,primes,pascal,sieve
program Primes(input,output); var candidates, primes : Array[0..999] of Integer; n, i, j : Integer; begin for i := 0 to 999 do begin candidates[i] := 1; end; candidates[0] := 0; candidates[1] := 0; i := 0; while i < 1000 do begin while (i < 1000) and (candidates[i] = 0)...

## for loop unintentionally breaking at if statement

javascript,if-statement,for-loop,primes
I am trying to determine the largest prime factor of a number by working backwards from the largest possible factor. Once a factor is found, I test to see if it is prime by using the PrimeTest3 function within the original function. However, it is not giving me the answer...

## make dynamic array larger [duplicate]

c++,arrays,dynamic,primes
This question already has an answer here: Using sizeof with a dynamically allocated array 5 answers This is for a non-graded challenge problem where I am looking to find as many prime numbers as fast as possible. One of the constraints is that I must use new/delete, so std::vector...

## How to find more clever algorithm to check pairs of primes to see if paired they produce another prime?

ruby,algorithm,primes,mathematical-optimization
I am stuck on Project Euler question 60. I know it is advised not too ask questions or find answers online about it, but otherwise I cannot find the motivation to continue. So I hope to find some help here which can make me go forward. So long for the...

## Better algorithm on prime numbers

python,algorithm,primes,python-3.4
I'm working on a program which will found the nth. prime number. For example, By listing the first six prime numbers: 2, 3, 5, 7, 11 and 13, we can see that the 6th prime is 13. I'm trying to making an algorithm, like, if I want to see 50th...

## Prime numbers using Sieve of Atkin with BigInteger

c#,math,primes,prime-factoring
Does anyone happen to know of a C# Sieve of Atkin algorithm using BigInteger? From my understanding, this is the best known prime factorization algorithm currently in existence. I currently have this function: /// <summary> /// Finds prime numbers using the Sieve of Atkins algorithm. /// </summary> /// <param name="max">The...

## Python prime checker

python,primes
I recently started learning python (by which I mean, 35 minutes ago at the time of posting...) and I've wrote a few things e.g. square root generator, factorial generator, Fibonacci number generator, prime checker etc. After I wrote the prime checker, I thought I'd try modifying it so that instead...

## I wish to create a program to implement prime-counting function for n<=10^14

primes
I could use Sieve of Eratosthenes to count the number of prime numbers but it would require me to create an array so large that it couldn't be created. I'm just looking forward to find a way or algorithm to achieve the task. A name or reference would serve the...

## Prime factorization python

python,primes,prime-factoring
I'm very new to python, and I thought that I would create a program that returns the prime factors of a given number. This is my code: import math import operator import functools def isprime (n): if n == 1: return False elif n == 2: return True else: for...

## Python - identifying if integer is a prime or not? Output prints both a prime and not a prime

python,primes
#Enter an integer num = int(input("Enter a number: ")) #Prime number is a positive integer that is evenly divisible by 1 and itself #Zero and one shouldn't be prime numbers #Use for loop in the range of 2 as the first prime to any integer num #If else statements: If...

## Python prime number function returning error in tutorial

function,python-2.7,debugging,primes
Python newbie here, so bear with me... Unfortunately there's no "support" for these tutorials, except posting questions in a Q&A forum and maybe another student can help. I know that there are a ton of Python prime functions out there, but I think I've come up with one that works....

## Primes generating perl

perl,primes
I'm trying to generate random prime number print Math::Prime::Util->random_strong_prime(128); But, when I call one of the methods (i tried various) of Math::Prime::Util, I get: Parameter 'Math::Prime::Util' must be a positive integer at /home/ivan/perl5/lib/perl5/x86_64-linux-thread-multi/Math/Prime/Util.pm line 400. I can't understend what's wrong, 128 is positive and integer. Script runs under Starman server(psgi)...

## HackerEarth Probelm: Reverse Primes

java,optimization,out-of-memory,primes
Generate as many distinct primes P such that reverse (P) is also prime and is not equal to P. Output: Print per line one integer( ≤ 10^15 ). Don't print more than 10^6 integers in all. Scoring: Let N = correct outputs. M = incorrect outputs. Your score will...

## Freezing goal in prolog

prolog,primes,sieve-of-eratosthenes,prolog-coroutining
I want to freeze my goal until some variable, for example list, is unbounded, right now I have sieve(N,L) :- freeze(Aux,sieve(N,L,[],Aux)), numlist(2,N,Aux). sieve(N,L,R,[H|T]) :- freeze(X, X mod H =\= 0 ; X == H), findall(X,select(X,T,_),P), sieve(N,L,[H|R],P). sieve(_,L,L,[]). But it stop after some operations and waits forever. Could someone tell me...

## to find a prime number in java

java,algorithm,primes
I came accros one of the solutions for finding if a number is prime as below : //checks whether an int is prime or not. boolean isPrime(int n) { if (n == 2){ return true; } //check if n is a multiple of 2 if (n%2==0){ return false; } //if...

## (Relatively) Quickly find some divisor for a number < 10 000 000

c#,math,primes
Assume for everything that I'm talking only about natural numbers less than 10 million. I'm looking to pre-generate a list of the Lowest Prime Divisor (LPD) for all numbers under 10 000 000. For example, LPD(14) == 2, LPD(15) == 3, and the LPD of any prime is itself. I...

## Prime factors using recursion in Java

java,algorithm,recursion,primes,prime-factoring
I'm having trouble with recursion in java. So I have the following method and i should transform it only with recursion without any loop. public static List<Integer> primesLoop(int n) { List<Integer> factors = new ArrayList<Integer>(); int f = 2; while (f <= n) if (n % f == 0) {...

## How does this isPrime function work?

c,primes
I was reading http://www2.informatik.hu-berlin.de/~weber/slipOff/hashmap_c.html and having hard time understanding how this function works: static unsigned long isPrime(unsigned long val) { int i, p, exp, a; for (i = 9; i--;) { a = (rand() % (val-4)) + 2; p = 1; exp = val-1; while (exp) { if (exp &...

## Python – Have a variable be both an int and a str

python,string,int,primes
Here is my code: def retest2(): print "Type in another chapter title! Or type \"Next\" to move on." primenumbers2() def primenumbers1(): print "--------------------------------------------------\nChapters in books are usually given the cardinal numbers 1, 2, 3, 4, 5, 6 and so on.\nBut I have decided to give my chapters prime numbers 2,...

## Check if a number is prime Using powershell

powershell,primes
This is my script to check if a random number is prime or not : [int]\$nombre = Get-Random -Minimum 1 -Maximum 10 \$nombre \$j=0 if(\$nombre -lt 2) { " \$nombre n'est pas premier " } else { for(\$i=1; \$i -le \$nombre; \$i++){ if( \$nombre%\$i -eq 0) {\$j++} } if(\$j -eq...

## What is the mistake in my code? Computing prime numbers upto n

javascript,for-loop,primes
function primesuntil(n) { var primes = [2]; for (i=3; i < n ; i++) { var j=0; while (j<primes.length) { var quotient = i/primes[j]; if (quotient !== math.floor(quotient) { var hasDivisor = false; j++; } else { var hasDivisor = true; j=primes.length+15; } } if (hasDivisor == false) {primes.push(i);} else...

## Prime number algorithm Objective C explanation please

objective-c,loops,for-loop,primes
Hi sorry for my bad english, i have a question guys, i'm learning objective c and i'm learning booleans right now, my question is: why when running the second loop in the code, the number 2 is taken as prime, i mean, as i see it p takes the value...

## Ruby - method for generating prime numbers

ruby,math,primes
I'm writing a method - prime_numbers - that, when passed a number n, returns an n number of primes. It should not rely on Ruby's Prime class. It should behave like so: prime_numbers 3 => [2, 3, 5] prime_numbers 5 => [2, 3, 5, 7, 11] My first attempt at...